Как выполнить поиск символа в любом порядке (12 букв, из которых 6 должно быть слово) с PHP?

Я думаю об этом весь день и, похоже, не могу понять эффективность памяти и быстрый способ. Проблема в:

например, у меня есть эти буквы: efjlnrrttuwx (12 букв)

Я ищу это слово TURTLE (6 букв)

Как найти все возможные слова в полном диапазоне (12 слов) с помощью php? (Или с python, если это может быть намного проще?)

Вещи, которые я пробовал:

Использование перестановок: я сделал все возможные строки, используя алгоритм перестановки, поместив их в массив (только 6 символов длиной) и сделайте in_array, чтобы проверить, совпадает ли оно с одним из слов в моем массиве с допустимыми словами (в этом случае, содержащие TURTLE, но иногда два или три слова). Этот калькулятор стоит много памяти и времени, особенно с 6 + символами, чтобы получить перестановки.
создавая регулярное выражение (я плохо в этом). Я хотел создать регулярное выражение, чтобы проверить, находится ли 6 из 12 (входных) символов в слове из «действительного массива». проблема в том, что мы не знаем, какая буква из 12 будет исходной позицией и позицией других слов.

Примером этого может быть: http://drawsomethingwords.net/

Надеюсь, вы можете помочь мне с этой проблемой, так как я действительно хотел бы это исправить. Спасибо за все ваше время 🙂

Я сталкивался с подобными проблемами при написании редактора кроссвордов (например, найти все слова длины 5 с «В» во второй позиции). В основном это сводится к:

Обработать список слов и упорядочить слова по длине (т. Е. Список всех слов длины 2, длины 3, длины 4 и т. Д.). Причина в том, что вы часто знаете длину слова (ов), которое вы хотите найти. Если вы хотите найти слова неизвестной длины, вы можете повторить поиск снова для другого списка слов.
Вставьте каждый отдельный список слов в дерево третичного поиска, что значительно ускорит поиск слов. Каждый узел в дереве содержит символ, и вы можете спуститься к дереву для поиска слов. Существуют также специализированные структуры данных, такие как trie, но я еще не изучил (пока).

Теперь для вашей проблемы вы можете использовать дерево поиска для записи функции поиска, такой как

function findWords($tree, $letters) { // ... }

где tree – tree поиска, содержащее слова длины, которую вы хотите найти, а letters – список допустимых символов. В вашем примере letters будет строка efjlnrrttuwx .

Дерево поиска позволяет вам искать слова, по одному символу за раз, и вы можете отслеживать символы, с которыми вы столкнулись. Пока эти символы находятся в списке допустимых букв, вы продолжаете поиск. Когда вы столкнулись с листовым узлом в дереве поиска, вы нашли существующее слово, которое вы можете добавить к результату. Если вы столкнулись с символом, который не находится в letters (или он уже использовался), вы можете пропустить это слово и продолжить поиск в другом месте в дереве поиска.

Мой редактор кроссвордов Palabra содержит реализацию вышеуказанных шагов (часть выполняется на Python, но в основном на C). Он работает достаточно быстро для списка слов по умолчанию Ubuntu, содержащего примерно 70 тыс. Слов.

Есть, вероятно, лучшие способы, но это просто не в моей голове:

Я предполагаю, что у вас есть база данных слов (например, словарь). Добавьте поля az в таблицу базы данных. Напишите сценарий, который суммирует количество каждой буквы в слове и записывает их в поля az как целое число. IE для воздушного шара, таблица будет выглядеть так:

 id name ab ... l ... n ... o 1 balloon 1 1 2 ... 1 ... 2

Затем, когда пользователь вводит слово, вы подсчитываете, сколько из каждого символа находится в этом слове и соответствует тому, что находится в базе данных.

 // User enters 'zqlamonrlob' // You count the letters: abcdefghijklmnopqrstu vwxyz 1 1 0 0 0 0 0 0 0 0 0 2 1 1 2 0 1 1 0 0 0 0 0 0 0 1 // Query the database $sql = "SELECT `name` FROM `my_table` WHERE `a` <= {$count['a'] AND `b` <= {$count['b'] ...}";

Это даст вам список слов, которые используют некоторые или все буквы, введенные пользователем.

Вот регулярное выражение, просто чтобы показать, что он может (но не обязательно должен ) быть выполнен:

 preg_match('/^(?:t()|u()|r()|t()|l()|e()|.)+$\1\2\3\4\5\6/i', 'efjlnrrttuwx')

Матчи.

Как это работает? Пустые скобки для скобок всегда совпадают, если соответствует предыдущее письмо. Обратные ссылки в конце регулярного выражения удостоверяются, что каждый из символов участвовал в матче. Следовательно,

 preg_match('/^(?:t()|u()|r()|t()|l()|e()|.)+$\1\2\3\4\5\6/i', 'efjlnrrtuwx')

(правильно) не будет соответствовать, потому что в строке есть только один t но для регулярного выражения требуется два разных t s.

Проблема в том, что, конечно, движок регулярных выражений должен проверить многие перестановки, чтобы прийти к такому выводу. В то время как успешное совпадение может быть довольно быстрым (175 шагов механизма регулярных выражений в первом случае), неудачная попытка совпадения может быть дорогостоящей (3816 шагов во втором случае).

Я думаю, вам нужно подойти к этой проблеме с противоположного направления.

Прокрутите список слов, проверяя слова с указанным количеством символов, чтобы увидеть, находятся ли слова в указанном наборе символов.