Как сделать подбор слов из словаря чтобы получилась заданная фраза (анаграммы)? Хочу сделать сервис на подобии этого: www.wordplays.com/anagrammer
Суть в следующем: пользователь вводит некую фразу. В ответ ему приходят предложения из слов, буквы которых все до одной присутствуют в исходной фразе. Слова берутся из базы.
Я пришел к тому, что каждому слову надо присвоить ключ, который представляет собой все символы слова упорядоченные по алфавиту. Например, слово "button". Ключем этого слова будет "bnootu".
Алгоритм сводится к следующему:Берем фразу которую ввел пользователь и составляем для нее ключ (из фразы убираем все кроме букв). Выбираем с помощью нехитрой регулярки из базы ключи, которые "входят" в исходный ключ, т.е. содержать только те буквы, которые есть в исходном ключе. Не все буквы могут в искомом ключе присутствовать, главное чтобы количество повторений не превышало количества повторений букв в исходном ключе. Например, если брать ключ "bnootu" как исходные, то для него может подойти ключ "botu". Из найденных ключей составляем комбинации так, чтобы в сумме эти ключи представляли собой исходный ключ. Из составленных комбинаций генерируем готовые фразы.
Собственно затык произошел с пунктом 3. Проблема заключается в том, что количество ключей в комбинации может варьироваться. Я смог решить эту задачу через рекурсию и перебор, но уперся в ограниченность ресурсов.
Поэтому интересно, есть ли какие нибудь варианты решения пункта 3 без рекурсии? А если даже и с рекурсией, то как избежать присутствия дупликатов комбинаций (например комбинации "ro ot" и "ot ro")?
Как сделать подбор слов из словаря чтобы получилась заданная фраза (анаграммы)? Хочу сделать сервис на подобии этого: www.wordplays.com/anagrammer
Суть в следующем: пользователь вводит некую фразу. В ответ ему приходят предложения из слов, буквы которых все до одной присутствуют в исходной фразе. Слова берутся из базы.
Я пришел к тому, что каждому слову надо присвоить ключ, который представляет собой все символы слова упорядоченные по алфавиту. Например, слово "button". Ключем этого слова будет "bnootu".
Алгоритм сводится к следующему:Берем фразу которую ввел пользователь и составляем для нее ключ (из фразы убираем все кроме букв). Выбираем с помощью нехитрой регулярки из базы ключи, которые "входят" в исходный ключ, т.е. содержать только те буквы, которые есть в исходном ключе. Не все буквы могут в искомом ключе присутствовать, главное чтобы количество повторений не превышало количества повторений букв в исходном ключе. Например, если брать ключ "bnootu" как исходные, то для него может подойти ключ "botu". Из найденных ключей составляем комбинации так, чтобы в сумме эти ключи представляли собой исходный ключ. Из составленных комбинаций генерируем готовые фразы.
Собственно затык произошел с пунктом 3. Проблема заключается в том, что количество ключей в комбинации может варьироваться. Я смог решить эту задачу через рекурсию и перебор, но уперся в ограниченность ресурсов.
Поэтому интересно, есть ли какие нибудь варианты решения пункта 3 без рекурсии? А если даже и с рекурсией, то как избежать присутствия дупликатов комбинаций (например комбинации "ro ot" и "ot ro")?
Суть в следующем: пользователь вводит некую фразу. В ответ ему приходят предложения из слов, буквы которых все до одной присутствуют в исходной фразе. Слова берутся из базы.
Я пришел к тому, что каждому слову надо присвоить ключ, который представляет собой все символы слова упорядоченные по алфавиту. Например, слово "button". Ключем этого слова будет "bnootu".
Алгоритм сводится к следующему:Берем фразу которую ввел пользователь и составляем для нее ключ (из фразы убираем все кроме букв). Выбираем с помощью нехитрой регулярки из базы ключи, которые "входят" в исходный ключ, т.е. содержать только те буквы, которые есть в исходном ключе. Не все буквы могут в искомом ключе присутствовать, главное чтобы количество повторений не превышало количества повторений букв в исходном ключе. Например, если брать ключ "bnootu" как исходные, то для него может подойти ключ "botu". Из найденных ключей составляем комбинации так, чтобы в сумме эти ключи представляли собой исходный ключ. Из составленных комбинаций генерируем готовые фразы.
Собственно затык произошел с пунктом 3. Проблема заключается в том, что количество ключей в комбинации может варьироваться. Я смог решить эту задачу через рекурсию и перебор, но уперся в ограниченность ресурсов.
Поэтому интересно, есть ли какие нибудь варианты решения пункта 3 без рекурсии? А если даже и с рекурсией, то как избежать присутствия дупликатов комбинаций (например комбинации "ro ot" и "ot ro")?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для решения этой проблемы можно воспользоваться алгоритмом обратной динамики. В данном случае можно создать матрицу, где строки будут представлять ключевые слова из базы, а столбцы будут представлять символы из исходной фразы. В каждой ячейке матрицы будет храниться информация о том, сколько символов из ключа можно использовать для составления фразы.
Затем, используя динамическое программирование, можно заполнить эту матрицу, начиная с нулевой строки (пустой ключ) и постепенно добавляя ключевые слова из базы. После заполнения матрицы, можно восстановить все возможные комбинации ключей, которые могут быть использованы для составления исходной фразы.
Что касается избежания дубликатов комбинаций, можно использовать множество (set) для хранения уже найденных комбинаций. Перед добавлением новой комбинации в множество, ее можно отсортировать, чтобы исключить дубликаты.
Таким образом, использование алгоритма обратной динамики позволит эффективно находить комбинации слов из базы, которые могут быть использованы для составления заданной фразы, а использование множества поможет избежать дубликатов комбинаций.