Я ищу эффективный алгоритм для скремблирования набора букв в перестановку, содержащую максимальное количество слов.
Например, скажем, мне дан список букв: {e, e, h, r, s, t}. Мне нужно упорядочить их таким образом, чтобы они содержали максимальное количество слов. Если я заказываю эти буквы в "theres", в них содержатся слова "the", "there", "her", "here" и "ere". Таким образом, этот пример может иметь 5 баллов, поскольку он содержит 5 слов. Я хочу упорядочить буквы таким образом, чтобы набрать наибольшее количество баллов (содержать как можно больше слов).
Наивным алгоритмом было бы попытаться оценить каждую перестановку. Я считаю, что это O (n!), Поэтому 720 различных перестановок будут опробованы только для 6 букв выше (включая некоторые дубликаты, поскольку в примере e дважды). Конечно, для большего количества букв наивное решение быстро становится невозможным.
Алгоритм не должен на самом деле создавать самое лучшее решение, но он должен найти хорошее решение за разумное время. Для моего приложения простое угадывание ( Монте-Карло ) для нескольких миллионов перестановок работает довольно плохо, так что в настоящее время этот показатель лучше.
В настоящее время я использую алгоритм Aho-Corasick для оценки перестановок. Он ищет каждое слово в словаре всего за один проход по тексту, поэтому я считаю, что это довольно эффективно. Это также означает, что все слова хранятся в trie , но если для другого алгоритма требуется другое хранилище, это тоже хорошо. Я не беспокоюсь о настройке словаря, просто время выполнения заказа и поиска. При необходимости можно использовать даже нечеткий словарь, например Bloom Filter .
Для моего приложения список букв составляет около 100, а словарь содержит более 100 000 записей. Словарь никогда не меняется, но необходимо заказать несколько разных списков букв.
Я рассматриваю попытку алгоритма поиска пути . Я полагаю, что я мог бы начать со случайной буквы из списка в качестве отправной точки. Затем каждая оставшаяся буква будет использоваться для создания «пути». Я думаю, что это будет хорошо работать с алгоритмом оценки Aho-Corasick, так как оценки могут быть построены по одной букве за раз. Я еще не пробовал найти путь; может это даже не хорошая идея? Я не знаю, какой алгоритм поиска пути может быть лучшим.
Другой алгоритм, о котором я подумал, также начинается со случайной буквы. Затем в словаре будет выполняться поиск «богатых» ветвей, содержащих оставшиеся буквы. Ветви словаря, содержащие недоступные буквы, будут удалены. Я немного запутался в деталях того, как это будет работать точно, но это может полностью исключить перестановки выигрышей.