Варианты слов из набора букв: Составление слов из заданного набора букв

Содержание

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

Вопрос задан 7 лет 6 месяцев назад

Изменён 7 лет 3 месяца назад

Просмотрен 9k раза

На вход программе подаётся набор английских букв. Имеется словарь из слов.

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

Пример

Входящий набор символов: hellomyfriend

Вывод программы:

Feed Hilly Morn
Feed Hilly Norm
Feed Horny Mill
Freehold Nil My
Refilled Hon My
Defiler Hymn Lo
и т.д.

Выбрать слова которые удовлетворяют входному набору символов у меня получилось. А вот быстро составлять из них предложения не получается.

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

Можете что-нибудь посоветовать?

php
алгоритм
математика
поиск

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

Важно для поиска:

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

Не важно:

порядок букв в словарном слове.
смысл слова.

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

Для быстрого нахождения слов с подходящим набором букв, но без учёта повторов, можно сделать битный индекс, как предложил @Mirdin: 26 букв английского алфавита = 26 бит. Пронумеровать слова в словаре (или просто индексом считать номер строки) и составить отдельный индекс в две колонки: id слова — битовая маска имеющихся букв. Для словаря меньше 65 тыс. слов, такой индекс будет «весить» 6 байт на слово, менее 400k. Можно держать в оперативной памяти для почти-мгновенного поиска. Так можно быстро найти например, первое слово фразы – просто, чтобы точно были выключены биты «лишних» букв.

Стоит сделать копию словаря, где буквы слова отсортированы по алфавиту, и слова отсортированы по алфавиту. Т.е. опять отдельный индекс: сортированные_буквы - id_слова. Этот индекс будет тяжелее самого словаря на (число слов * 2 или 3 байта). В этом индексе можно быстро находить подходящие слова и отбрасывать точно-неподходящие.

Алгоритм примерно такой. Ищем первое слово. Хочется найти первое же слово наибольшей возможной длины. Перебор по длине, от большего к меньшему. Ест допустимый набор букв и длина. Нашли первое слово, обновили допустимый набор букв и длины слов – ищем следующее слово.

Делаете структуру (таблицу в БД, хеш-таблица, словарь и тд что там есть в пхп) из двух полей на запись: хэш и собственно говоря слово. Забиваем эту структуру словами.
Хэш примерно делается так: индекс буквы в алфавите — степень двойки, все буквы слова складываем (32 бит для русского языка должно хватить). Это простейший вариант, возможно будет необходимо придумать более сложную функцию.
Получив слово которое надо заанаграмить — вычисляем его хэш и ищем по нему в нашей структуре

UPD: Это для одного слова, с фразами будет сложнее, но принцип тот же

Зарегистрируйтесь или войдите

Регистрация через Google

Регистрация через Facebook

Регистрация через почту

Отправить без регистрации

Почта

Необходима, но никому не показывается

Отправить без регистрации

Почта

Необходима, но никому не показывается

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Приложение Повар слов — Составь слова из набора букв — «Как отвлечься от мира, чуть напрягая мозг? »

Иногда хочется «потупить» в экран телефона, не напрягаясь и не думая о чём-то насущном. Но смотреть мемасики=деградировать. И чтобы не испытывать угрызения совести, я решила скачать данное приложение. Кстати, попалось оно мне в рекомендациях во время просмотров коротких роликов в отдельном приложении.