Python: Найти все анаграммы предложения

Question

Я хочу найти все возможные анаграммы из фразы, например, если я буду вводить «Дональд Трамп», я должен получить «Штиф-грязь», «Влажный старый рун» и, возможно, еще сотни.

У меня есть словарь около 100 000 слов, никаких проблем нет.

Но единственный способ, по которому я могу думать, - это прокрутить словарь и добавить все слова, которые могут быть созданы из ввода в список. Затем прокрутите список и если длина слова меньше длины ввода, петля через словарь снова добавит все возможные слова, которые могут быть сделаны из оставшихся букв, которые сделают его длиной ввода или меньше. И продолжайте цикл, пока у меня не будет всех комбинаций допустимых слов длины, равной входной длине.

Но это сложность O (n!), И потребовалось бы почти всегда бежать. Я попробовал.

Есть ли способ подойти к этой проблеме, чтобы сложность была меньше? Возможно, я нашел что-то в сети для perl, но я абсолютно не могу читать perl-код, особенно не perl golf.

Answer 1

Мне нравится ваша идея фильтровать список слов вплоть до слов, которые могут быть сделаны с помощью ввода букв, и мне нравится идея попытаться связать их вместе, но я думаю, что есть несколько основных оптимизаций, которые вы может привести к тому, что, скорее всего, ускорит ситуацию.

Для начала, вместо того, чтобы выбирать слово, а затем повторное сканирование всего словаря для того, что осталось, я бы подумал, что просто проделаю один фильтр, чтобы найти все возможные слова, которые могут быть сделаны с буквами, которые у вас есть. , Ваш словарь, вероятно, будет довольно колоссальным (150 000+, я подозреваю), поэтому повторное сканирование после каждого момента принятия решения будет совершенно неосуществимым. Когда у вас есть набор слов, которые вы можете законно использовать в анаграмме, оттуда вы останетесь с проблемой поиска, какие комбинации из них могут быть использованы для формирования полной анаграммы предложения.

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

Чтобы сделать это, я бы использовал рекурсию возврата, где в каждой точке вы сохраняете гистограмму оставшихся букв. Вы можете использовать это, чтобы отфильтровать слова, которые не могут быть добавлены больше, и это существенно экономит вам стоимость проверки всего словаря каждый раз. Я бы предположил, что эта рекурсия будет очень тупиковой, и что вы, вероятно, найдете все свои ответы без особых усилий.

Вы можете рассмотреть некоторые другие эвристики на этом пути. Например, сначала вы можете начать с более крупных слов, чтобы вытащить как можно больше букв и сохранить коэффициент ветвления на низком уровне. Для этого вы можете отсортировать список слов от самого длинного до кратчайшего и попробовать слова в этом порядке. В качестве альтернативы вы можете попытаться сначала использовать самые ограниченные буквы, чтобы уменьшить коэффициент ветвления. Такие эвристики, вероятно, будут работать на практике.

В целом вы все еще смотрите на экспоненциальную работу в худшем случае, но это не должно быть слишком плохо для более коротких строк.