Як скласти пропозицію з букв, введених користувачем stack overflow російською

На вхід програмі подається набір англійських букв. Є словник з слів.

Як згенерувати такі пропозиції з слів, щоб кожне з пропозицій полягала тільки з тих букв, що були подані на вхід, з огляду на кількість повторень.

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

Вибрати слова які задовольняють вхідного набору символів у мене вийшло. А ось швидко складати з них пропозиції не виходить.

Я робив методом перебору всіх слів. Для фрази myfavoritegame скрипт відпрацьовував близько 5 хвилин. На сайті пропозиції віддаються миттєво.

Можете що-небудь порадити?

заданий 28 Серпня '15 о 7:43

Ще раджу подивитися на системи пошуку, типу Sphinx - Rikaz 28 Серпня '15 в 8:25

Питання у вас звучить "Як зробити підбір слів з словника щоб вийшла задана фраза", а в прикладі ви приводі пошук анаграм. Чи не могли б ви прояснити свою задачу яким небудь прикладом. - Ruslan 28 Серпня '15 о 8:53

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

1. наявність букв в слові. Виключаємо містять букви поза заданих. Виключаємо, у міру складання фрази, вже використані.
2. вважаємо літери. У будь-який момент складання фрази відомо, слова якої довжини підходять, або точно не підходять.
3. повтори букв.

1. порядок букв в словниковому слові.
2. сенс слова.

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

Для швидкого знаходження слів з відповідним набором літер, але без урахування повторів, можна зробити бітний індекс, як запропонував @Mirdin: 26 букв англійського алфавіту = 26 біт. Пронумерувати слова в словнику (або просто індексом вважати номер рядка) і скласти окремий індекс в дві колонки: id слова - бітова маска наявних букв. Для словника менше 65 тис. Слів, такий індекс буде "важити" 6 байт на слово, менш 400k. Можна тримати в оперативній пам'яті для майже-миттєвого пошуку. Так можна швидко знайти наприклад, перше слово фрази - просто, щоб точно були вимкнені біти "зайвих" букв.

Варто зробити копію словника, де букви слова відсортовані за алфавітом. і слова відсортовані за алфавітом. Тобто знову окремий індекс: сортірованние_букви - id_слова. Цей індекс буде важче самого словника на (число слів * 2 або 3 байти). У цьому індексі можна швидко знаходити відповідні слова і відкидати точно-невідповідні.

Алгоритм приблизно такий. Шукаємо перше слово. Хочеться знайти перше ж слово найбільшою можливою довжини. Перебір по довжині, від більшого до меншого. Їсть допустимий набір букв і довжина. Знайшли перше слово, оновили допустимий набір букв і довжини слів - шукаємо наступне слово.

відповідь дан 28 Серпня '15 о 20:59

1. Робите структуру (таблицю в БД, хеш-таблиця, словник і тд що там є в пхп) з двох полів на запис: хеш і власне кажучи слово. Забиваємо цю структуру словами.
2. Хеш приблизно робиться так: індекс букви в алфавіті - ступінь двійки, всі букви слова складаємо (32 біт для української мови повинно вистачити). Це найпростіший варіант, можливо буде необхідно придумати більш складну функцію.
3. Отримавши слово яке треба заанаграміть - обчислюємо його хеш і шукаємо по ньому в нашій структурі

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

відповідь дан 28 Серпня '15 в 7:59

повторювана літера зіпсує всю малину. Слово "free", у "e" індекс 4, в суму піде два рази по 2 ^ 4, а це те саме, що 2 ^ 5, літера "f". - Sergiks 28 Серпня '15 о 20:49

@Sergiks, та тут ви маєте рацію, я описав самий простий випадок, на практиці доведеться користуватися чим небудь складніше. - Mirdin 29 Серпня '15 о 4:32