Algorithmus zum Gruppieren von Anagrammwörtern

Question

Bei einer Reihe von Wörtern müssen wir die Anagrammwörter finden und jede Kategorie alleine mithilfe des besten Algorithmus anzeigen.

Eingabe:

man car kile arc none like

Ausgabe:

man
car arc
kile like
none

Die beste Lösung, an der ich gerade arbeite, basiert auf einer Hashtabelle, aber ich überlege, wie ich eine Gleichung entwickeln kann, um Anagrammwörter in einen ganzzahligen Wert umzuwandeln.

Beispiel: man => 'm'+'a'+'n' aber das würde keine eindeutigen Werte liefern.

Irgendwelche Vorschläge?

---

Sieh dir den folgenden Code in C# an:

string line = Console.ReadLine();
string []words=line.Split(' ');
int[] numbers = GetUniqueInts(words);
for (int i = 0; i < words.Length; i++)
{
    if (table.ContainsKey(numbers[i]))
    {
        table[numbers[i]] = table[numbers[i]].Append(words[i]);
    }
    else
    {
        table.Add(numbers[i],new StringBuilder(words[i]));
    }

}

Das Problem besteht darin, die Methode GetUniqueInts(string []) zu entwickeln.

Answer 1

Anagramme können folgendermaßen gefunden werden:

1. Die Länge des Wortes sollte übereinstimmen.
2. Führe die Addition jedes Zeichens in Bezug auf den Ganzzahlenwert durch. Diese Summe stimmt überein, wenn du dasselbe bei einem Anagramm durchführst.
3. Führe die Multiplikation jedes Zeichens in Bezug auf den Ganzzahlenwert durch. Der berechnete Wert stimmt überein, wenn du dasselbe bei einem Anagramm durchführst.

Also dachte ich, dass wir durch die oben genannten drei Überprüfungen Anagramme finden können. Korrigiere mich, wenn ich falsch liege.

---

Beispiel: abc cba

Die Länge beider Wörter beträgt 3.

Die Summe der einzelnen Zeichen für beide Wörter beträgt 294.

Das Produkt der einzelnen Zeichen für beide Wörter beträgt 941094.

Answer 2

Nur eine einfache Python-Lösung hinzufügen, zusätzlich zu den anderen nützlichen Antworten:

def check_permutation_group(word_list):
    result = {}

    for word in word_list:
        hash_arr_for_word = [0] * 128  # angenommen standard ascii

        for char in word:
            char_int = ord(char)
            hash_arr_for_word[char_int] += 1

        hash_for_word = ''.join(str(item) for item in hash_arr_for_word)

        if not result.get(hash_for_word, None):
            result[str(hash_for_word)] = [word]
        else:
            result[str(hash_for_word)] += [word]

return list(result.values())

Answer 3

Python-Code:

line = "man car kile arc none like"
hmap = {}
for w in line.split():
  ws = ''.join(sorted(w))
  try:
    hmap[ws].append(w)
  except KeyError:
    hmap[ws] = [w]

for i in hmap:
   print hmap[i]

Ausgabe:

['car', 'arc']
['kile', 'like']
['none']
['man']

Answer 4

JavaScript-Version. Verwendung von Hashing.

Zeitkomplexität: 0(nm), wobei n die Anzahl der Wörter und m die Länge des Wortes ist

var words = 'cat act mac tac ten cam net'.split(' '),
    hashMap = {};

words.forEach(function(w){
    w = w.split('').sort().join('');
    hashMap[w] = (hashMap[w]|0) + 1;
});

function print(obj,key){ 
    console.log(key, obj[key]);
}

Object.keys(hashMap).forEach(print.bind(null,hashMap))