Как найти жизнеспособные комбинации букв для игры?

Question

Я пытаюсь научить себя iOS, клонируя популярную игру для Android, но есть часть игры, в которой я не могу понять, как решить, в языковом агностическом смысле.

Игра очень проста: игроку даются 6 букв, различные подмножества которых могут образовывать около 30 различных трехбуквенных, 4-буквенных и 5-буквенных слов. Игрок должен найти как можно больше этих возможных слов за две минуты. Игра может похвастаться 4000 различными 6-буквенными комбинациями для отличной повторной игры.

Я не могу понять, как автор получил 4000 различных комбинаций.

Я имею в виду, что я мог найти 4000 уникальных комбинаций из 6 букв, но как я могу найти то, что имеет около 30 жизнеспособных подкомбинаций? Если есть слишком мало жизнеспособных слов, которые могут быть сделаны из букв или слишком много, это не сработает, и пространство слишком велико, чтобы просто пройти через это грубой силой, я думаю, поскольку это предполагает проверку 165 миллионов комбинации против словаря тысяч слов.

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

Answer 1

Подсказка: вы начинаете со словаря/списка слов, а затем удаляете слова из списка, которые вы не можете сделать, используя именно ваши 6 заданных букв.

(или любой другой. Ваша проблема объяснения немного неясно.)

В худшем случае вы должны проверить количество слов, которые находятся в списке (намного меньше, чем 165 миллионов). И есть другие трюки, которые можно использовать для ускорения поиска.

Answer 2

Вы пробовали выборку 6 букв в случайном порядке? Вы можете просто пробовать наборы из 6 букв, пока не найдете тот, у которого есть много возможных слов, и повторите 4000 раз. Тестирование каждого из них не должно занять слишком много времени, потому что есть только 2^6 = 64 подмножества, и вы можете индексировать словарь слова, чтобы быстро проверять эти подмножества. Вы также можете настроить вероятности разных букв, чтобы найти хорошие наборы с большей вероятностью.

Несколько более сложный подход, который часто хорошо подходит для этого типа проблем, - это цепь Маркова Монте-Карло (http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo). Вы можете попытаться заменить несколько букв за раз, придавая более высокий вес наборам из 6, которые близки к целевому количеству возможных слов.

Answer 3

Один из способов сделать это.

Получите список 6-буквенных и меньших слов. Я не знаю, сколько это будет. Вероятно, порядка 100 000. Но даже удвоить это не имеет большого значения.

Теперь соберите буквы в каждом слове. Итак, «кедры» становятся «актерами». Они становятся ключами в словаре, причем значения в словаре являются действительными словами, которые сопоставляются с этими буквами. Таким образом, запись для «acders» будет включать в себя «кедры» и «испуганные» и любые другие шестибуквенные слова, если таковые имеются, которые составлены из этих букв.

Теперь произвольно выберите три двухбуквенных слова из списка. Это дает вам 6-буквенную комбинацию.

Из этого вы можете создать свои перестановки.У вас есть потенциал:

6 one-letter words 
15 two-letter words 
20 three-letter words 
15 four-letter words 
6 five-letter words 
1 six-letter words 

Таким образом, вы должны сделать 63 словарных поиска, чтобы определить, сколько хороших слов у вас есть.

В английском языке есть 114 two-letter words, что означает, что существует 240 464 возможных комбинаций из трех двухбуквенных слов. Таким образом, вам придется делать порядка 15 миллионов поисковых запросов. Это займет несколько секунд.