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

Überhaupt nicht mit einer benutzerdefinierten Hash-Funktion zu beschäftigen. Verwenden Sie die normale String-Hash-Funktion auf Ihrer Plattform. Wichtig ist, den Schlüssel für Ihre Hashtabelle als die Idee eines "sortierten Wortes" zu machen - wobei das Wort nach Buchstaben sortiert ist, also "Auto" => "Acr". Alle Anagramme haben das gleiche "sortierte Wort".

Haben Sie einfach einen Hash von "sortiertem Wort" zu "Liste von Wörtern für dieses sortierte Wort". In LINQ ist dies unglaublich einfach:

using System;
using System.Collections.Generic;
using System.Linq;

class FindAnagrams
{
    static void Main(string[] args)
    {
        var lookup = args.ToLookup(word => SortLetters(word));

        foreach (var entry in lookup)
        {
            foreach (var word in entry)
            {
                Console.Write(word);
                Console.Write(" ");
            }
            Console.WriteLine();
        }
    }

    static string SortLetters(string original)
    {
        char[] letters = original.ToCharArray();
        Array.Sort(letters);
        return new string(letters);
    }
}

Beispielverwendung:

c:\Users\Jon\Test>FindAnagrams.exe man car kile arc none like
man
car arc
kile like
none

Answer 2

Ich habe ein von Godel inspiriertes Schema verwendet:

Weisen Sie den Primzahlen P_1 bis P_26 die Buchstaben zu (in beliebiger Reihenfolge, aber um kleine Hash-Werte zu erhalten, ist es am besten, häufig verwendten Buchstaben kleine Primzahlen zuzuweisen).

Erstellen Sie ein Histogramm der Buchstaben im Wort.

Dann ist der Hash-Wert das Produkt jeder Buchstaben zugeordneten Primzahl, hochgehoben zur Potenz seiner Häufigkeit. Dies gibt jedem Anagramm einen eindeutigen Wert.

Python-Code:

primes = [2, 41, 37, 47, 3, 67, 71, 23, 5, 101, 61, 17, 19, 13, 31, 43, 97, 29, 11, 7, 73, 83, 79, 89, 59, 53]

def get_frequency_map(word):
    map = {}

    for letter in word:
        map[letter] = map.get(letter, 0) + 1

    return map

def hash(word):
    map = get_frequency_map(word)
    product = 1
    for letter in map.keys():
        product = product * primes[ord(letter)-97] ** map.get(letter, 0)
    return product

Dies verwandelt clever das knifflige Problem, Subanagramme zu finden, in das (auch als knifflig bekannte) Problem, große Zahlen zu faktorisieren...

Answer 3

Eine Python-Version zum Spaß:

from collections import defaultdict
res = defaultdict(list)
L = "car, acr, bat, tab, get, cat".split(", ")

for w in L:
    res["".join(sorted(w))].append(w)

print(res.values())

Answer 4

Ich glaube nicht, dass Sie etwas Besseres finden werden als eine Hashtabelle mit einer benutzerdefinierten Hash-Funktion (die die Buchstaben des Wortes vor dem Hashen sortieren würde).

Die Summe der Buchstaben wird nie funktionieren, weil Sie 'ac' und 'bb' nicht wirklich unterschiedlich machen können.

Answer 5

Sie benötigen große Ganzzahlen (oder eigentlich einen Bit-Vektor), aber Folgendes könnte funktionieren

Das erste Vorkommen jedes Buchstabens erhält die Bit-Nummer für diesen Buchstaben, das zweite Vorkommen erhält die Bit-Nummer für diesen Buchstaben + 26.

Zum Beispiel

a #1 = 1 b #1 = 2 c #1 = 4 a #2 = 2^26 b #2 = 2 ^ 27

Diese können dann zusammengezählt werden, um einen eindeutigen Wert für das Wort basierend auf seinen Buchstaben zu erhalten.

Ihre Speicheranforderungen für die Wortwerte werden sein:

n * 26 Bits

wo n die maximale Anzahl der Vorkommen eines beliebigen wiederholten Buchstabens ist.