Wie überprüft man, ob zwei Listen in Python zirkulär identisch sind?

Zunächst kann dies in O(n) in Bezug auf die Länge der Liste gemacht werden Sie können feststellen, dass, wenn Sie Ihre Liste 2 mal duplizieren ( [1, 2, 3] ) [1, 2, 3, 1, 2, 3] ist, dann wird Ihre neue Liste definitiv alle möglichen zyklischen Listen enthalten.

Sie müssen also nur überprüfen, ob die Liste, die Sie suchen, innerhalb eines 2-fachen der Startliste liegt. In Python können Sie dies auf folgende Weise erreichen (vorausgesetzt, dass die Längen gleich sind).

Einige Erklärungen zu meinem oneliner: list * 2 kombiniert eine Liste mit sich selbst, map(str, [1, 2]) konvertiert alle Zahlen in einen String und ' '.join() konvertiert das Array ['1', '2', '111'] in einen String '1 2 111' .

Wie einige Leute in den Kommentaren darauf hingewiesen haben, kann oneliner möglicherweise einige falsche Positive geben, um alle möglichen Randfälle zu erfassen:

P.S.1 Wenn Sie über die zeitliche Komplexität sprechen, sollten Sie beachten, dass O(n) erreicht wird, wenn die Teilzeichenfolge in O(n) time gefunden werden kann. Es ist nicht immer so und hängt von der Implementierung in Ihrer Sprache ab (, obwohl es möglicherweise in linearer Zeit KMP zum Beispiel möglich ist) ).

P.S.2 für Leute, die Angst haben, Strings zu betreiben und aufgrund dieser Tatsache denken, dass die Antwort nicht gut ist. Was ist wichtig, Komplexität und Geschwindigkeit? Dieser Algorithmus läuft möglicherweise in O(n) time und O(n) space, was ihn viel besser macht als alles in O(n^2) domain. Um dies selbst zu sehen, können Sie einen kleinen Benchmark ausführen (erstellt eine Zufallsliste, öffnet das erste Element und fügt es an das Ende an, um eine zyklische Liste zu erstellen. Sie können Ihre eigenen Manipulationen durchführen)

0,3 Sekunden auf meiner Maschine. Nicht wirklich lange. Versuchen Sie nun, dies mit O(n^2) solutions zu vergleichen. Während es vergleicht, können Sie von den USA nach Australien reisen (wahrscheinlich von einem Kreuzfahrtschiff)

Nicht genug in Python genug, um dies in der von Ihnen gewünschten Sprache zu beantworten, aber in C / C ++ würde ich die Nullen und Einsen in Bits umwandeln und sie auf die niedrigstwertigen Bits eines uint64_t schieben . Dies ermöglicht Ihnen, alle 55 Bits in einem Schlag zu vergleichen - 1 Uhr.

Schrecklich schnell, und das Ganze passt in On-Chip-Caches (209.880 Bytes). Hardware-Unterstützung zum gleichzeitigen Verschieben aller 55 Listenmitglieder ist nur in den Registern einer CPU verfügbar. Gleiches gilt für den Vergleich aller 55 Mitglieder gleichzeitig. Dies ermöglicht eine Eins-zu-Eins-Zuordnung des Problems zu einer Softwarelösung. (und die Verwendung der SIMD / SSE 256-Bit-Register, bei Bedarf bis zu 256 Mitglieder) Als Ergebnis ist der Code für den Leser sofort offensichtlich.

Vielleicht können Sie das in Python implementieren, ich weiß es einfach nicht gut genug, um zu wissen, ob das möglich ist oder wie die Leistung sein könnte.

Nachdem wir darauf geschlafen hatten, wurden einige Dinge offensichtlich und alles zum Besseren.

1.) Es ist so einfach, die kreisförmig verknüpfte Liste mit Bits zu drehen, für die Dalis cleverer Trick nicht nötig ist. Innerhalb eines 64-Bit-Registers wird das Standard-Bit-Shifting die Rotation sehr einfach durchführen und in einem Versuch, dies alles Python-freundlicher zu machen, indem arithmetische anstelle von Bit-Ops verwendet wird.

2.) Die Bitverschiebung kann einfach durch Division durch 2 erreicht werden.

3.) Das Ende der Liste für 0 oder 1 zu überprüfen, kann einfach mit Modulo 2 durchgeführt werden.

4.) Das Verschieben einer 0 in den Kopf der Liste vom Ende aus kann durch Division durch 2 erfolgen. Wenn nämlich die Null tatsächlich verschoben würde, würde dies das 55. Bit falsch machen, was es bereits tut absolut nichts.

5.) "Bewegen" eine 1 an den Kopf der Liste vom Schwanz kann durch Dividieren von 2 und Hinzufügen von 18.014.398.509.481.984 - das ist der Wert durch die Markierung der 55. Bit wahr und alle übrigen false erstellt werden.

6. Wenn ein Vergleich zwischen dem Anker und dem zusammengesetzten uint64_t nach einer gegebenen Drehung TRUE ist, brechen Sie auf und geben Sie TRUE zurück.

Ich würde das gesamte Array von Listen direkt in ein Array von uint64_ts konvertieren, um zu vermeiden, dass die Konvertierung wiederholt durchgeführt werden muss.

Nachdem ich ein paar Stunden damit verbracht habe, den Code zu optimieren und die Assemblersprache zu studieren, konnte ich die Laufzeit um 20% reduzieren. Ich sollte hinzufügen, dass der O / S und MSVC Compiler gestern ebenfalls mittags aktualisiert wurde. Aus welchen Gründen auch immer, die Qualität des vom C-Compiler erzeugten Codes hat sich nach dem Update (15.11.2014) dramatisch verbessert. Laufzeit ist jetzt ~ 70 Takte, 17 Nanosekunden um einen Ankerring mit allen 55 Windungen eines Testrings zu vergleichen und zu vergleichen und NxN aller Ringe gegen alle anderen erfolgt in 12,5 Sekunden .

Dieser Code ist so eng, dass alle bis auf 4 Register in 99% der Fälle nichts tun. Die Assemblersprache entspricht dem C-Code fast Zeile für Zeile. Sehr leicht zu lesen und zu verstehen. Ein tolles Montageprojekt, wenn sich jemand das selbst beibrachte.

Hardware ist Hazwell i7, MSVC 64-bit, volle Optimierungen.

Wenn Sie zwischen den Zeilen lesen, klingt es so, als ob Sie einen Vertreter jeder zirkulären Äquivalenzklasse von Strings mit 3 Einsen und 52 Nullen aufzählen möchten. Wechseln wir von einer dichten Repräsentation zu einer spärlichen (drei Zahlen in range(55) ). In dieser Darstellung ist die zirkulare Verschiebung von s by k durch das Verständnis set((i + k) % 55 for i in s) gegeben. Der lexikografische Minimum-Repräsentant in einer Klasse enthält immer die Position 0. Bei einer Menge der Form {0, i, j} mit 0 < i < j sind die anderen Kandidaten für das Minimum in der Klasse {0, j - i, 55 - i} und {0, 55 - j, 55 + i - j} . Daher benötigen wir (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j)) für das Original als Minimum. Hier ist ein Aufzählungscode.

In Anbetracht der Tatsache, dass Sie so viele Vergleiche machen müssen, lohnt es sich vielleicht, einen ersten Durchlauf durch Ihre Listen zu machen, um sie in eine Art von kanonischer Form zu konvertieren, die leicht verglichen werden kann?

Versuchen Sie, eine Reihe von kreisförmig eindeutigen Listen zu erhalten? Wenn dies der Fall ist, können Sie sie nach der Konvertierung in Tupel in ein Set werfen.

Entschuldigung David Eisenstat dafür, dass er seine Antwort nicht gefunden hat.

Bauen Sie weiter auf RocketRoys Antwort: Wandle alle deine Listen in vorzeichenlose 64-Bit-Nummern um. Drehen Sie diese 55 Bits für jede Liste, um den kleinsten numerischen Wert zu finden.

Sie haben jetzt einen einzelnen vorzeichenlosen 64-Bit-Wert für jede Liste, den Sie direkt mit dem Wert der anderen Listen vergleichen können. Die Funktion is_circular_identical () wird nicht mehr benötigt.

(Im Wesentlichen erstellen Sie einen Identitätswert für Ihre Listen, der nicht von der Rotation der Listenelemente beeinflusst wird.) Das würde sogar funktionieren, wenn Sie eine beliebige Anzahl von Einsen in Ihren Listen haben.

Wie andere bereits erwähnt haben, können Sie, sobald Sie die normalisierte Rotation einer Liste gefunden haben, diese vergleichen.

Hier ist ein Arbeitscode, der das macht, Die grundlegende Methode besteht darin, für jede Liste eine normalisierte Rotation zu finden und zu vergleichen:

• Berechne einen normalisierten Rotationsindex für jede Liste.
• Überstreiche beide Listen mit ihren Offsets, vergleiche jedes Element und gib es zurück, wenn sie nicht übereinstimmen.

Beachten Sie, dass diese Methode nicht von Zahlen abhängt, Sie können Listen mit Strings übergeben (alle Werte, die verglichen werden können).

Anstatt eine List-in-List-Suche zu machen, wissen wir, dass die Liste mit dem Minimalwert beginnen soll - also können wir die Minimalwerte durchlaufen und suchen, bis wir herausfinden, welche die niedrigsten aufeinanderfolgenden Werte hat für weitere Vergleiche, bis wir das Beste haben.

Es gibt viele Möglichkeiten, bei der Berechnung des Index früh zu beenden, Details zu einigen Optimierungen.

• Überspringt die Suche nach dem besten Mindestwert, wenn nur einer vorhanden ist.
• Überspringt die Suche nach Mindestwerten, wenn der vorherige Wert ebenfalls ein Mindestwert ist (es wird niemals eine bessere Übereinstimmung sein).
• Überspringt die Suche, wenn alle Werte gleich sind.
• Frühzeitig fehlschlagen, wenn Listen unterschiedliche Mindestwerte haben.
• Verwenden Sie den regulären Vergleich, wenn Offsets übereinstimmen.
• Passen Sie Offsets an, um zu vermeiden, dass die Indexwerte während des Vergleichs in eine der Listen eingeschlossen werden.

Beachten Sie, dass in Python eine List-in-List-Suche zwar schneller sein könnte, ich jedoch einen effizienten Algorithmus finden wollte, der auch in anderen Sprachen verwendet werden könnte. Außerdem ist es von Vorteil, das Erstellen neuer Listen zu vermeiden.

Siehe: dieses Snippet für weitere Tests / Beispiele.

Sie können überprüfen, ob eine Liste A einer zyklischen Verschiebung der Liste B in der erwarteten O (N) -Zeit ziemlich leicht entspricht.

Ich würde eine Polynom-Hash-Funktion verwenden, um den Hash der Liste A und jede zyklische Verschiebung von Liste B zu berechnen. Wo eine Verschiebung von Liste B den gleichen Hash wie Liste A hat, würde ich die tatsächlichen Elemente vergleichen, um zu sehen, ob Sie sind gleich.

Der Grund dafür ist, dass Sie mit polynomialen Hash-Funktionen (die extrem häufig sind!) den Hash jeder zyklischen Verschiebung von der vorherigen in konstanter Zeit berechnen können, sodass Sie Hashwerte für alle zyklischen Verschiebungen berechnen können in O (N) Zeit.

Es funktioniert so:

Nehmen wir an, B hat N Elemente, dann ist der Hash von B mit Primzahl P:

Dies ist eine optimierte Methode zum Auswerten eines Polynoms in P und entspricht:

Beachten Sie, wie jedes B [i] mit P ^ (N-1-i) multipliziert wird. Wenn wir B um 1 nach links verschieben, wird jeder B [i] mit Ausnahme des ersten um ein zusätzliches P multipliziert. Da Multiplikation über Addition verteilt wird, können wir alle Komponenten auf einmal multiplizieren, indem wir einfach den gesamten Hash multiplizieren und dann den Faktor für das erste Element korrigieren.

Der Hash der linken Verschiebung von B ist nur

Die zweite Verschiebung nach links:

und so weiter ...

HINWEIS: Alle obigen Berechnungen werden modulo einer Maschinenwortgröße durchgeführt, und Sie müssen nur einmal P ^ N berechnen.