Anagramme (Schüttelwörter) gruppieren

C++ :: Aufgabe #343

2 Lösungen

Anagramme (Schüttelwörter) gruppieren

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

Lösungen:

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 << " }";
}

Bitte melden Sie sich an um eine Kommentar zu schreiben.

Kommentar schreiben

von JKooP (18090 Punkte) - 23.04.2021 um 09:29 Uhr

C++ 17

C-Code

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<vector<string>> group_anagrams(vector<string>& vs) {
    vector<vector<string>> vr;
    unordered_map<string, vector<string>> um;

    for (auto i{ 0 }; i < vs.size(); i++) {
        auto t{ vs[i] };
        sort(t.begin(), t.end());
        um[t].push_back(vs[i]);
    }
    for (const auto& i : um)
        vr.push_back(i.second);

    return vr;
}

int main()
{
    vector<string> s{ { "eat", "tea", "tan", "ate", "nat", "bat" } };

    for (const auto& i : group_anagrams(s)) {
        for (const auto& k : i)
            cout << k << ", ";
        cout << endl;
    }
}

Bitte melden Sie sich an um eine Kommentar zu schreiben.

Kommentar schreiben