Anagramme (Schüttelwörter) gruppieren

2 Lösungen

#343

Fortgeschrittener - C++ von JKooP - 13.03.2021 um 12:41 Uhr

Von einem Anagramm oder auch deutsch Schüttelwort spricht man,
wenn man durch Umstellen der vorhandenen Zeichen eines Wortes ein neues sinnvolles Wort bilden kann.
Oft werden Anagramme mit Palindromen verwechselt, wobei ein Anagramm auch gleichzeitig
ein Palindrom sein kann, z.B.: LAGERREGAL – REGALLAGER.

ANNA – ANNA hingegen ist kein Anagramm, sondern ein Palindrom,
obwohl es wegen des Gleichklangs ANA oft irrtümlich so bezeichnet wird.

Gegeben ist eine Liste bestehend aus verschiedenen Wörtern.
list = { "eat", "tea", "tan", "ate", "nat", "bat" };

Schreibe eine Methode/Funktion, die die Liste list auf Anagramme hin überprüft
und die Ergebnisse in einer neuen Liste gruppiert zurückgibt.

result = { {"bat"}, {"nat", "tan"}, {"ate", "eat", "tea"} }

Die Reihenfolge der Rückgabe in der List ist nicht entscheidend.
Wörter, die keine Anagramme bilden, sollen ebenfalls als Einzelwort in die Ergebnisliste aufgenommen werden.
Je nach Programmiersprache oder Vorliebe können statt Listen auch Arrays oder Tupel verwendet werden.

Viel Spaß

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von felixTheC (1200 Punkte) - 12.04.2021 um 22:24 Uhr

C-Code

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

using std::cout;
using std::endl;
using std::vector;
using std::string;
using std::set;

void find_anagrams(const vector<string> &list);
vector<string> is_annagram(const vector<string> &anagram_list, const string &data, vector<string> &known_data);
void print_results(const vector<vector<string>>& data);
string set_to_string(const set<char> &set1);


int main()
{
    vector<string> list = { "eat", "tea", "tan", "ate", "nat", "bat" };
    find_anagrams(list);
    return 0;
}

void find_anagrams(const vector<string> &list)
{
    vector<string> know_strings;
    vector<vector<string>> results;

    for (const auto &val : list)
    {
        auto result = is_annagram(list, val, know_strings);
        if (!result.empty())
        {
            results.push_back(result);
        }
    }

    // result is {  {eat, tea, ate} {tan, nat} {bat} }
    print_results(results);
}

vector<string> is_annagram(const vector<string> &anagram_list, const string &data, vector<string> &known_data)
{

    set<char> data_set = set<char>(data.begin(), data.end());
    vector<string> results;

    if (std::find(known_data.begin(), known_data.end(), set_to_string(data_set)) != known_data.end())
    {
        return vector<string>();
    }
    else
    {
        known_data.push_back(set_to_string(data_set));

        for (const auto &val : anagram_list)
        {
            set<char> tmp_set = set<char>(val.begin(), val.end());
            if (tmp_set == data_set)
            {
                results.push_back(val);
            }
        }
        return results;
    }
}

string set_to_string(const set<char> &set1)
{
    string new_string;
    for (auto val : set1)
    {
        new_string += val;
    }

    return new_string;
}

void print_results(const vector<vector<string>>& data)
{
    cout << "{ ";
    for (auto value : data)
    {
        cout << " {";
        for (auto val = value.begin(); val != value.end(); ++val)
        {
            cout << *val;
            if (val != value.end() - 1)
            {
                cout << ", ";
            }
        }
        cout << "}";
    }
    cout << " }";
}