Учитывая таблицу букв и список слов, найдите N слов, используя все буквы

Question

Я ищу эффективный алгоритм, чтобы сделать следующее.

Учитывая таблицу / словарь подсчета букв

counts = {'a': 3, 'b': 2, 'd': 2, 'e': 2, 'k':2, 'r': 2 }

и список М слов

words = ['break, 'add', 'build' ... ]

написать функцию, которая находит N слов, используя все буквы (и слова из списка)

>>> find_words(counts, words, 3)
['break', 'break', 'add']

Наивный подход обойти все слова N раз слишком медленно (я думаю, что это O (m ^ n)).

Answer 1

Эта проблема имеет сильно NP-полное чувство. Поэтому я ожидаю, что не будет действительно эффективного решения.

Поэтому я бы посоветовал вам попытаться свести ее к известной проблеме и решить ее вместо этого. В частности, вы можете преобразовать это в целочисленную задачу линейного программирования. Решатели для тех часто удивительно хороши. И согласно Python Mixed Integer Linear Programming есть число, которое вам доступно относительно легко.

Конкретная проблема, которую вы пытаетесь решить, заключается в следующем. Вы пытаетесь найти вектор из m целых чисел x_i такой, что 0 ≤ x_i, sum(x_i) ≤ n, а для каждой буквы l сумма, сколько раз использовалась буква, не превышает вашего количества. Целевая функция, которую вы хотели бы максимизировать, представляет собой сумму x_i * (1 + len(w_i)), где w_i - это i '-е слово.

Это всегда даст ответ. Ответ, который вы получите, будет представлять решение вашей проблемы тогда и только тогда, когда целевая функция равна n плюс количество доступных букв. Если целевая функция меньше этого, то никакого решения не существует.