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

Question

Я реализую игру, в которой игрок может запросить предложение, а компьютер должен вернуть слово с наибольшим количеством очков.Чтобы сделать это, я должен начать со слова, а из него я должен добавить буквы (от 1 до 7), чтобы создать новое слово, которое существует.

Пример:

• Слово:
• Буквы: y, m, s, i, r, e, s
• Возможные новые слова: они, они, их, там, тезис, термины и т. Д.

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

Answer 1

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

E.g.

Слово:

Буквы: y, m, s, i, r, e, a

• первая перестановка y, m,s, i, r, e, a

  • размер 1 => они,
  • размер 2 => они
  • ...

• вторая перестановка m, y, s, i, r, e, a

  • размер 1 => их
  • размер 2 => их
  • ...

Вот пример

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    std::string word{"the"};
    std::string letters{"ymsirea"};
    std::sort(letters.begin(), letters.end());
    do {
        for (std::size_t i(1); i <= letters.length(); ++i) {
            std::cout << word << letters.substr(0, i) << std::endl;
        }
    } while (std::next_permutation(letters.begin(), letters.end()));

    return 0;
}

Другое решение - добавить специальный символ к буквам, таким как \n и переставлять буквы.Затем вы сравниваете новое слово, пока не появится специальный символ

Слово:

Буквы: y, m, s, i, r, e, a, \ 0

• первая перестановка y, \ 0, m, s, i, r, e, a => они
• вторая перестановка y, m, \ 0, s, i, r, e, a => их

Вот пример:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    std::string word{"the"};
    std::string letters{"ymsirea\n"};
    std::sort(letters.begin(), letters.end());
    do {
        std::size_t pos = letters.find('\n');
        if (pos > 0)
            std::cout << word << letters.substr(0, pos) << std::endl;
    } while (std::next_permutation(letters.begin(), letters.end()));

    return 0;
}

Оба алгоритма будут генерировать много дубликатов.Оба алгоритма будут генерировать до (n)! * N слов, где n - количество букв.В этом примере будет произведено 7 * 6 * 5 * 4 * 3 * 2 * 7 = 35280 слов.Если в письмах есть дубликаты, std :: next_permutation пропустит некоторые перестановки.Вы можете использовать набор для фильтрации дубликатов.Может быть максимум 7 + 7 * 6 + 7 * 6 * 5 + 7 * 6 * 5 * 4 + 7 * 6 * 5 * 4 * 3 + 7 * 6 * 5 * 4 * 3 * 2 = 8659разные слова, если все буквы уникальны.Таким образом, эти алгоритмы производят до 35280-8659 = 26621 дубликатов.

Для перестановки вы можете использовать std :: next_permutation

Answer 2

Найти анаграммы просто, для каждого слова ассоциируйте ключ, который является тем же словом, с отсортированной буквой.Например: orange -> aegnor.Затем создайте словарь, ключом которого является ранее определенный ключ, а значением которого является список слов, имеющих этот ключ.

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

Например, словарь будет содержать:

dict["aegnor"] -> [ "orange", "organe" ]

Пример:

input: "the"

First pass:
Key = "eht"
dict["eht"] -> [ "the" ]

Second pass, we add the letter 'm':
Key = "ehmt"
dict["ehmt"] -> [ "meth", "them" ]

...

Answer 3

Почему бы не использовать встроенный алгоритм?

На этой странице даже есть пример, который вы можете использовать.

https://en.cppreference.com/w/cpp/algorithm/next_permutation

Просто переберите все перестановки,предварительно добавьте «и» и найдите его в своем словаре.