Как я могу оптимизировать перестановки слов в игре 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]