Предупреждение: я редко использую PHP, поэтому он имеет дело только с общим алгоритмом, который должен работать практически на любом языке, а не чем-то специфичным для PHP.
Предположительно, у вас есть слово, в котором буквы былипереставить, и вы хотите найти, какие слова могут быть сделаны из этих букв.
Если это правильно, общая идея довольно проста: взять копию списка слов и отсортировать буквы в каждомслово в алфавитном порядке.Поместите отсортированные и несортированные версии каждого слова рядом и отсортируйте все по отсортированным словам (но сохраняя каждое несортированное слово вместе с его отсортированной версией).Возможно, вы захотите свернуть дубликаты вместе, чтобы (например) вместо {abt: bat} и {abt: tab} у вас было: {abt: bat, tab}
Затем, чтобы сопоставитьскремблируй слово, сортируй буквы в алфавитном порядке.Ищите совпадения в своем словаре (поскольку он отсортирован, вы можете использовать бинарный поиск).Когда вы найдете совпадение, результатом будет слово (или слова), связанное с этой группой отсортированных букв.Используя приведенный выше пример, если зашифрованное слово было «tba», вы бы отсортировали его, чтобы получить «abt», затем найдите «abt», чтобы получить «bat» и «tab».
Редактировать: как@ Морон указал в комментариях, сортировка и бинарный поиск не являются по сути важными моментами сами по себе.Основные пункты - превратить все эквивалентные входные данные в идентичные ключи, а затем использовать какой-то быстрый поиск по ключу, чтобы найти слово (а) для этого ключа.
Сортировка букв в каждом слове - это простой способ превратить эквивалентные вводы в идентичные клавиши.Сортировка списка и выполнение двоичного поиска - один из простых способов быстрого поиска по ключу.
В обоих случаях существует довольно много альтернатив.Я совсем не уверен, что альтернативы могут значительно улучшить производительность, но они, безусловно, могли бы.
Например, вместо простого бинарного поиска вы могли бы иметь второй уровень индекса, который говорит вам, гдеклавиши, начинающиеся с «а», были клавиши, начинающиеся с «б», и так далее.Учитывая, что несколько чрезвычайно часто используемых букв находятся в начале алфавита (например, 'e' и 'a'), вам может лучше отсортировать слова так, чтобы относительно необычные буквы ('q ',' z 'и т. д.) направлены к передней части клавиши, а наиболее часто используемые буквы - в конце.Это дало бы первому поиску, основанному на начальном символе, наибольшую дискриминацию.
Что касается сортировки / бинарного поиска, возможно, существует больше альтернатив и, вероятно, более убедительные аргументы в пользу использования чего-то еще.Хеш-таблицы обычно разрешают поиск в (почти) постоянном времени.Попытки могут существенно сократить объем памяти, особенно когда многие слова имеют общий префикс.Единственным очевидным недостатком является то, что код для любого из них, вероятно, является более трудоемким (хотя тип массива PHP основан на хэше, так что вы, вероятно, могли бы использовать его довольно хорошо).