Как составить предложение из букв, введенных пользователем?

На вход программе подаётся набор английских букв. Имеется словарь из слов.
Как сгенерировать такие предложения из слов, чтобы каждое из предложений состояло только из тех букв, что были поданы на вход, учитывая количество повторений.
Пример
Входящий набор символов: hellomyfriend
Вывод программы:
Feed Hilly Morn Feed Hilly Norm Feed Horny Mill Freehold Nil My Refilled Hon My Defiler Hymn Lo и т.д.

Выбрать слова которые удовлетворяют входному набору символов у меня получилось. А вот быстро составлять из них предложения не получается.
Я делал методом перебора всех слов. Для фразы myfavoritegame скрипт отрабатывал около 5 минут. На сайте предложения отдаются мгновенно.
Можете что-нибудь посоветовать?

Ответ

Предположим, вам нужно просто найти все возможные комбинации слов из данного словаря, удовлетворяющие условию. Не отвлекаясь на особенности именно языка.
Важно для поиска:
наличие букв в слове. Исключаем содержащие буквы вне заданных. Исключаем, по мере составления фразы, уже использованные. считаем буквы. В любой момент составления фразы известно, слова какой длины подходят, или точно не подходят. повторы букв.
Не важно
порядок букв в словарном слове. смысл слова.
Для скорости нужно сделать поиск по важным признакам максимально быстрым, при необходимости убрав неважные аспекты.
Для быстрого нахождения слов с подходящим набором букв, но без учёта повторов, можно сделать битный индекс, как предложил @Mirdin: 26 букв английского алфавита = 26 бит. Пронумеровать слова в словаре (или просто индексом считать номер строки) и составить отдельный индекс в две колонки: id слова - битовая маска имеющихся букв. Для словаря меньше 65 тыс. слов, такой индекс будет "весить" 6 байт на слово, менее 400k. Можно держать в оперативной памяти для почти-мгновенного поиска. Так можно быстро найти например, первое слово фразы – просто, чтобы точно были выключены биты "лишних" букв.
Стоит сделать копию словаря, где буквы слова отсортированы по алфавиту, и слова отсортированы по алфавиту. Т.е. опять отдельный индекс: сортированные_буквы - id_слова. Этот индекс будет тяжелее самого словаря на (число слов * 2 или 3 байта). В этом индексе можно быстро находить подходящие слова и отбрасывать точно-неподходящие.
Алгоритм примерно такой. Ищем первое слово. Хочется найти первое же слово наибольшей возможной длины. Перебор по длине, от большего к меньшему. Ест допустимый набор букв и длина. Нашли первое слово, обновили допустимый набор букв и длины слов – ищем следующее слово.