Finden äquivalente Wörter in einer Liste durch willkürliche Zuordnung

Question

Stellen Sie sich eine Liste von Wörtern haben:

['cat', 'ant', 'bro', 'gro'] 

eine beliebige Abbildung verwenden, die wir selbst {'c'=>'a', 'a'=>'n', 't'=>'t' } konstruieren, können wir ‚Katze‘ auf ‚Ameise‘ Karte, und in ähnlicher Weise Wir können eine beliebige Zuordnung finden, um 'bro' in 'gro' umzuwandeln.

Dies ist die Idee, Wörter zu finden, die gleichwertig sind. Ich schrieb eine Funktion, die zwei Wörter vergleicht und prüft, ob sie äquivalent durch eine Mapping-I on the fly konstruieren:

def compareWords(w1, w2): 
    mapping = {} 
    for i in xrange(0, len(w1)): 
     if w1[i] in map: 
      if mapping[w1[i]] == w2[i]: 
       continue 
      else: 
       return False 
     else: 
      mapping[w1[i]] = w2[i] 

    return True 

Beispiel Eingabe:

['cat', 'ant', 'bro', 'gro'] 

Beispiel Ausgang:

[['cat','ant'], ['bro', 'gro']]

Die Verwendung dieser Funktion für jedes Wortpaar in der Liste, um eine Ausgabeliste von Listen äquivalenter Wörter zurückzugeben, läuft in O (n^2), da jedes Paar t benötigt o verglichen werden. Ich habe diesen Teil, bei dem ich diese Methode oben verwende, nicht in der Eingabeliste implementiert und die Ausgabeliste generiert, da diese Methode nicht der effiziente Vergleich ist, nach dem ich suche. Gibt es eine Möglichkeit in O (n) Zeit äquivalente Wörter in dieser Liste zu finden?

Weitere Erläuterung: Wenn ich eine Liste von Worten, und ich möchte alle „gleichwertig“ Worte zu finden, würde ich brauchen, um die Kontrollen in Wortpaaren zu machen. Wenn alle Buchstaben der Wörter, die ich vergleiche, eindeutig sind, dann ist ein anderes Wort in der Liste nur äquivalent zu diesem ersten Wort, wenn alle Buchstaben in dem zweiten Wort ebenfalls eindeutig sind. Daher kann abc auf xyz abgebildet werden, wenn xyz in der Liste ist. xyz kann auf pqr abgebildet werden, wenn sich xyz in der Liste befindet. In Anbetracht dessen sind abc, xyz und pqr alle gleichwertig. Das ist die Art von Gruppierung, nach der ich suche.

Answer 1

Wenn ich richtig verstanden habe, suchen Sie nach einer Möglichkeit zu überprüfen, ob eine beliebige Beziehung, als eine Liste von Paaren x,y eine Funktion ist, das heißt x1==x2 bedeutet y1==y2. Dies kann leicht mit Sätzen erfolgen:

def is_function(rel): 
    return len(set(rel)) == len(set(x for x, y in rel)) 


print is_function(['ab', 'cd', 'xd']) # yes 
print is_function(['ab', 'cd', 'ad']) # no 

Zwei Wörter „gleichwertig“ im Sinne Ihrer Frage sind, ob ihr Brief zu Brief Beziehung ist eine Funktion:

def equivalent(a, b): 
    return is_function(zip(a, b)) 

print equivalent('foo', 'baa') # yes 
print equivalent('foo', 'bar') # no 

Wenn Sie Äquivalenzen betrachten zwischen verschiedenen Wörtern als unterschiedliche Relationen, gibt es keine Möglichkeit, den Vergleich mit jedem zu vermeiden. Darüber hinaus ist Ihre "Äquivalenz" nicht einmal kommutativ, A ~ B bedeutet nicht B ~ A (z.B. abc ~ xyx, sondern xyx !~ abc).

Aus Ihrem Kommentar erweist sich Ihre Beziehung als bijektiv (Hinweis: Ihr Code ist in diesem Fall nicht korrekt). Die einfachste (nicht unbedingt effiziente) Möglichkeit, die Liste in "Äquivalenzklassen" aufzuteilen, wäre die Berechnung eines "Hash" für jedes Wort, wobei Buchstaben durch Zahlen ersetzt werden, wobei 0 für den ersten Buchstaben, 1 für den zweiten usw. steht:

def eq_hash(word): 
    return tuple(word.index(c) for c in word) 

print eq_hash('mom') # 0 1 0 
print eq_hash('dad') # 0 1 0 

Jetzt können Sie alle Wörter gruppieren, die den gleichen "Hash" haben.Diese werden im Rahmen Ihrer Frage entsprechen:

group = {} 

words = ['mom', 'dad', 'aaa', 'bob', 'ccc', 'xyz', 'abc'] 

for w in words: 
    h = eq_hash(w) 
    group[h] = group.get(h, []) + [w] 

print group.values() 
# [['xyz', 'abc'], ['mom', 'dad', 'bob'], ['aaa', 'ccc']] 

Answer 2

Wenn ich Ihre Anfrage zu verstehen, Sie wollen Gruppen Worte, so dass jeder Beziehung einzigartig sein könnte, nicht unbedingt, dass es einzigartig ist. Mit deinen Beispielen, Mama ~ Papa ~ bab, aber schlecht könnte nicht in diesem Satz existieren, da keine Zuordnung, die von Mama zu Papa (m-> d, o-> a) oder Papa zu bab (d-> b) zuordnen kann, a-> a) kann zu schlecht (für Mama, m-> b UND d? für Papa, d bis b einmal und überspringen die nächste?).

Unter der Annahme, dass Ihre Gruppierung wirklich kommutativ ist, sollten Sie, sobald Sie ein Wort gruppiert haben, es nie wieder besuchen, außer um das erste Wort jeder Gruppe zu überprüfen.

So würden Sie beginnen, indem Sie Ihr erstes Wort zu Ihrer ersten Gruppe hinzufügen. Für jedes weitere Wort müssen Sie es dann mit dem ersten Wort in jeder vorhandenen Gruppe vergleichen. Wenn es übereinstimmt, fügen Sie es der Gruppe hinzu. Wenn sie keiner Gruppe entspricht, fügen Sie sie einer neuen Gruppe hinzu.

Im schlimmsten Fall ist dies O (N ** 2), wenn jedes Wort in Ihrer Gruppe zu einer eigenen Gruppe gehört. Im besten Fall, wenn alle Wörter in Ihrem Satz in der ersten Gruppe enden, wäre es O (N), da Sie nur das erste Wort in der einzigen Gruppe mit jedem zusätzlichen Wort vergleichen würden. Wenn Sie eine log (N) Verteilung von Mengen haben, ist dieser Algorithmus effektiv O (N log (N)). Es hängt also von Ihrem Eingabe-Set ab, aber es wird viel weniger Vergleiche ergeben, als wenn Sie jedes Paar überprüfen.