Как сделать подбор слов из словаря чтобы получилась заданная фраза (анаграммы)?

Question

[Андрей Ивченков]

Хочу сделать сервис на подобии этого:
www.wordplays.com/anagrammer
Суть в следующем: пользователь вводит некую фразу. В ответ ему приходят предложения из слов, буквы которых все до одной присутствуют в исходной фразе. Слова берутся из базы.
Я пришел к тому, что каждому слову надо присвоить ключ, который представляет собой все символы слова упорядоченные по алфавиту. Например, слово "button". Ключем этого слова будет "bnootu".
Алгоритм сводится к следующему:

1. Берем фразу которую ввел пользователь и составляем для нее ключ (из фразы убираем все кроме букв).
   
2. Выбираем с помощью нехитрой регулярки из базы ключи, которые "входят" в исходный ключ, т.е. содержать только те буквы, которые есть в исходном ключе. Не все буквы могут в искомом ключе присутствовать, главное чтобы количество повторений не превышало количества повторений букв в исходном ключе. Например, если брать ключ "bnootu" как исходные, то для него может подойти ключ "botu".
   
3. Из найденных ключей составляем комбинации так, чтобы в сумме эти ключи представляли собой исходный ключ.
   
4. Из составленных комбинаций генерируем готовые фразы.
   

Собственно затык произошел с пунктом 3. Проблема заключается в том, что количество ключей в комбинации может варьироваться. Я смог решить эту задачу через рекурсию и перебор, но уперся в ограниченность ресурсов.
Поэтому интересно, есть ли какие нибудь варианты решения пункта 3 без рекурсии? А если даже и с рекурсией, то как избежать присутствия дупликатов комбинаций (например комбинации "ro ot" и "ot ro")?

Comments

[Mrrl]

Какая примерно длина фразы (в буквах)? Если ограничить 30 буквами, то можно подумать

Answer 1

[Mrrl]

Многомерная задача о рюкзаке.

Допустим, у нас есть фраза "aaabbc" и словарь

aab
abb
abc
bbcc
aac

Для фразы считаем, сколько раз в ней встретилась каждая буква. Буква 'a' встречается na=3 раза, буква 'b' - nb=2 раза, буква 'c' - nc=1 раз.
Заводим битовый массив B с размерностями 0..na, 0..nb. 0..nc (в нашем примере это 24 бита). В элемент (0,0,0) кладём 1, в остальные 0.

1000 0000
0000 0000
0000 0000

Теперь перебираем слова из словаря. Для каждого слова считаем количество каждой буквы в нём (для aab это ma=2,mb=1,mc=0), и строим массив B1, в котором B1[a,b,c] = B[a,b,c] | B[a-ma,b-mb,c-mc] (для отрицательных индексов считаем значения нулевыми). В нашем случае получится

1000 0000
0010 0000
0000 0000

Продолжаем для остальных слов. После добавления каждого слова проверяем элемент B[na,nb,nc]. Если он ненулевой - мы нашли вариант (правда, помним из него только последнее слово - остальные восстановим на следующих проходах). Вариант запомним, элемент B[na,nb,nc] обнулим.
У нас получится:

abb=(1,2,0)

1000 0000
0010 0000
0100 0000

abc=(1,1,1)

1000 0000
0010 0100
0100 0001

Первый вариант есть - он кончается на "abc". Обнуляем B[3,2,1] и продолжаем.
Слово bbcc=(0,2,2) можно не рассматривать, в нём mc > nc.

aac=(2,0,1)

1000 0010
0010 0100
0100 0001

Нашли второй вариант - кончается на "aac". Слова в словаре кончились.

Теперь надо построить фразу "aab" из словаря

aab
abb

и фразу "abb" из словаря

aab
abb
abc
bbcc

Теоретически, это можно делать одновременно - но придётся отслеживать несколько индеков. И обнулять их уже нельзя, надо смотреть, не пытаются ли в них записать 1 (даже если там уже было значение 1).
Если на массив у вас есть 2 ГБ памяти, а разных букв не более 26, то этого хватит на фразу из 39 букв (худший случай - когда 13 букв встречаются по 1 разу, а 13 по 2 раза).