Как я могу оптимизировать перестановки слов в игре Scrabble?

Question

Я пытаюсь сделать логику для противника в игре с царапинами.

Я много думал и пришел к выводу, что мне нужно использовать anagrams и проверить эти анаграммы на список слов в файле словаря, чтобы узнать, является ли сгенерированное слово на самом деле словом, содержащимся в словаре файл.

Вопрос, который у меня есть, - optimization. Поскольку эта анаграмма использует recursion и работает до 8 факториалов, существует, как правило, много «мусорных» слов, которые не существуют в любом словаре, например, повторения одной буквы.

Должна быть какая-то проверка, чтобы проверить, действительны ли перестановки, а не только повторение 1 символа. До сих пор я не понимаю, как это сделать: быстро и точно.

На английском языке слова, как представляется, формируются как гласными, так и согласными. Я думал проверить, содержит ли слово хотя бы 1 гласный и по крайней мере 1 согласный, однако есть некоторые исключения, когда слова могут содержать только гласные или только согласные. Поэтому этот метод выходит из окна.

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

---

Мой вопрос:

Может кто-нибудь предложить метод, который будет работать 100% времени, чтобы оптимизировать число перестановок генерироваться?

---

Мне не нужны бесполезные генерироваться и они оказываются большая часть того, что генерируется.

Я считаю это хорошим подходом, но в то же время я считаю, что я должен упустить что-то, что намного быстрее и более подходящее для того, чего я хочу достичь.

Если кто-нибудь может предложить способ проверить, действительно ли слова жизнеспособны или нет, или если вы могли бы предложить лучший способ приблизиться к ситуации, было бы весьма полезно.

Спасибо.

Answer 1

(Ограничение: псевдокод может быть недействительным java, хотя это выглядит так)

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

Две строки являются анаграммами друг друга, если они сравнивают одинаковые при сортировке их обоих. Превращение порядка букв в ваше кандидатское слово, чтобы узнать, является ли какой-либо из них легальными английскими словами. Вместо этого, сортировать письма и сравнить ее с вашим списком слов:

boolean is_anagram(string word_a, string word_b){ 
    return sorted(word_a).equals(sorted(word_b)); 
} 

List<string> valid_anagrams(string candidate_word){ 
    anagrams = new List<string>(); 
    foreach(string word : list_of_words){ 
     if (is_anagram(candidate, word)){ 
      anagrams.push(word); 
     } 
    } 
    return anagrams; 
} 

Это более эффективно, если количество слов в списке слов меньше, чем факториал размера вашего слова кандидата. Например, количество легальных слов в словах с друзьями составляет около 170 000, поэтому вы предпочли бы вышеупомянутый метод проверки слов длиной 9 или более.

Если вы планируете проверять много слов-кандидатов, вы можете сэкономить время, сохранив отсортированные формы всех ваших действительных слов. Создайте словарь, в котором ключ является отсортированной строкой, а значение представляет собой список английских слов, которые являются анаграммами этой строки. Он должен выглядеть следующим образом:

{ 
    "act": ["act", "cat", "tab"], 
    "abll": ["ball"], 
    "aeprs": ["asper", "parse", "pears", "reaps", "spare", "spear"] 
} 

Вы можете построить этот словарь один раз в начале программы, например, так:

d = new Dictionary<string, List<string>>(); 
foreach (string word in list_of_words){ 
    string key = sorted(word) 
    if (!d.contains_key(key)){ 
     d[key] = new List<string>(); 
    } 
    d[key].push(word); 
} 

затем найти действительные анаграммы для строки просто вопрос получения доступа к Словарь.

List<string> valid_anagrams(string candidate_word){ 
    string key = sorted(candidate_word); 
    if (!d.contains_key(key)){ 
     return new List<string>(); 
    } 
    else{ 
     return d[key]; 
    } 
} 

Answer 2

Вы можете построить бинарное дерево (ы) из вашего словаря или взвешенный график, а затем просто пересечь график (ы) с вашими анаграммами, если вам нужен быстрый способ проверить ваши анаграммы. Это может стать дорогостоящим в памяти, в зависимости от размера вашего словаря, и для построения графика (ов) может потребоваться некоторое время при инициализации.

Если вы идете по маршруту нескольких графиков, вы можете создать график для каждой буквы алфавита, а затем создать соединение 1-й степени с каждой буквой, следующей за этой буквой в словаре.

Итак, у вас есть словарь [и, рука, муравьев, в, муравьи, беспокойная, армия]

вы бы иметь график, как следует:

[a][ar:1][an:3] 
[ar][arm:2] 
[an]["":0][and:1][ant:2] 
[arm]["":0][army:1] 
[and]["":0] 
[ant]["":0][ants:2] 
[ants]["":0][antsy:1] 
[army]["":0] 
[antsy]["":0]