Zyklische Wörter
Problemstellung
Wir können uns ein zyklisches Wort als ein Wort vorstellen, das in einem Kreis geschrieben ist. Um ein zyklisches Wort darzustellen, wählen wir eine beliebige Startposition und lesen die Zeichen im Uhrzeigersinn. "Bild" und "turepisch" sind also Darstellungen für dasselbe zyklische Wort.
Sie erhalten ein String [] -Wort, von dem jedes Element ein zyklisches Wort darstellt. Gibt die Anzahl der verschiedenen zyklischen Wörter zurück, die dargestellt werden.
Schnellste Gewinne (Big O, wobei n = Anzahl der Zeichen in einer Zeichenfolge)
word-puzzle
counting
fastest-algorithm
Eierbeine
quelle
quelle
Antworten:
Python
Hier ist meine Lösung. Ich denke, es könnte immer noch O (n 2 ) sein, aber ich denke, der durchschnittliche Fall ist viel besser als das.
Grundsätzlich funktioniert es, indem jede Zeichenfolge so normalisiert wird, dass jede Drehung dieselbe Form hat. Beispielsweise:
Die Normalisierung erfolgt durch Suchen nach dem Mindestzeichen (durch Zeichencode) und Drehen der Zeichenfolge, sodass sich das Zeichen an der letzten Position befindet. Wenn dieses Zeichen mehrmals vorkommt, werden die Zeichen nach jedem Vorkommen verwendet. Dies gibt jedem zyklischen Wort eine kanonische Darstellung, die als Schlüssel in einer Karte verwendet werden kann.
Die Normalisierung ist im schlimmsten Fall n 2 (wobei jedes Zeichen in der Zeichenfolge gleich ist, z. B.
aaaaaa
), aber die meiste Zeit wird es nur wenige Vorkommen geben, und die Laufzeit wird näher seinn
.Auf meinem Laptop (Dual Core Intel Atom bei 1,66 GHz und 1 GB RAM)
/usr/share/dict/words
dauert das Ausführen (234.937 Wörter mit einer durchschnittlichen Länge von 9,5 Zeichen) etwa 7,6 Sekunden.quelle
Wieder Python (3)
Die Methode, die ich verwendet habe, bestand darin, einen rollierenden Hash jedes Wortes zu berechnen, beginnend mit jedem Zeichen in der Zeichenfolge. Da es sich um einen rollierenden Hash handelt, benötigt O (n) (wobei n die Wortlänge ist) Zeit, um alle n Hashes zu berechnen. Die Zeichenfolge wird als Basis-1114112-Nummer behandelt, wodurch sichergestellt wird, dass die Hashes eindeutig sind. (Dies ähnelt der Haskell-Lösung, ist jedoch effizienter, da die Zeichenfolge nur zweimal durchlaufen wird.)
Dann überprüft der Algorithmus für jedes Eingabewort seinen niedrigsten Hash, um festzustellen, ob er bereits in der Menge der gesehenen Hashes enthalten ist (eine Python-Menge, daher ist die Suche in der Größe der Menge O (1)). Wenn dies der Fall ist, wurde das Wort oder eine seiner Rotationen bereits gesehen. Andernfalls wird dieser Hash zum Set hinzugefügt.
Das Befehlszeilenargument sollte der Name einer Datei sein, die ein Wort pro Zeile enthält (wie
/usr/share/dict/words
).quelle
Haskell
Ich bin mir nicht sicher über die Effizienz, höchstwahrscheinlich ziemlich schlecht. Die Idee ist, zuerst alle möglichen Rotationen aller Wörter zu erstellen, die Werte zu zählen, die die Zeichenfolgen eindeutig darstellen, und das Minimum auszuwählen. Auf diese Weise erhalten wir eine Nummer, die für eine zyklische Gruppe eindeutig ist.
Wir können nach dieser Nummer gruppieren und die Anzahl dieser Gruppen überprüfen.
Wenn n die Anzahl der Wörter in der Liste und m die Länge eines Wortes ist, wird die 'zyklische Gruppennummer' für alle Wörter berechnet
O(n*m)
, sortiertO(n log n)
und gruppiertO(n)
.quelle
Mathematica
Beschlossen, wieder von vorne zu beginnen, jetzt, wo ich die Spielregeln verstehe (glaube ich).
Ein 10000-Wörter-Wörterbuch mit eindeutigen zufällig zusammengesetzten "Wörtern" (nur Kleinbuchstaben) der Länge 3. In ähnlicher Weise wurden andere Wörterbücher erstellt, die aus Zeichenfolgen der Länge 4, 5, 6, 7 und 8 bestehen.
g
nimmt die aktuelle Version des Wörterbuchs zur Überprüfung. Das oberste Wort wird mit zyklischen Varianten verbunden (falls vorhanden). Das Wort und seine Übereinstimmungen werden an die Ausgabelisteout
der verarbeiteten Wörter angehängt . Die Ausgabewörter werden aus dem Wörterbuch entfernt.f
läuft durch alle Wörter Wörterbuch.Beispiel 1 : tatsächliche Wörter
Beispiel 2 : Künstliche Wörter. Wörterbuch der Zeichenketten der Länge 3. Zuerst das Timing. Dann die Anzahl der Zykluswörter.
Timings als Funktion der Wortlänge . 10000 Wörter in jedem Wörterbuch.
Ich weiß nicht besonders, wie ich die Ergebnisse in Bezug auf O interpretieren soll. In einfachen Worten, das Timing verdoppelt sich ungefähr vom Drei-Zeichen-Wörterbuch zum Vier-Zeichen-Wörterbuch. Das Timing erhöht sich fast vernachlässigbar von 4 auf 8 Zeichen.
quelle
Dies kann in O (n) erfolgen, wobei eine quadratische Zeit vermieden wird. Die Idee ist, den Vollkreis zu konstruieren, der die Basiszeichenfolge zweimal durchläuft. Also konstruieren wir "Amazingamazin" als Vollkreis-String, um alle zyklischen Strings zu überprüfen, die "Amazing" entsprechen.
Unten ist die Java-Lösung:
quelle
Ich weiß nicht, ob das sehr effizient ist, aber dies ist mein erster Riss.
quelle
Perl
Ich bin mir nicht sicher, ob ich das Problem verstehe, aber dies entspricht zumindest dem Beispiel @dude in den Kommentaren. Bitte korrigieren Sie meine sicherlich falsche Analyse.
Für jedes Wort W in den angegebenen N Wörtern der Zeichenfolgenliste müssen Sie im schlimmsten Fall alle Zeichen von W durchlaufen. Ich muss davon ausgehen, dass die Hash-Operationen in konstanter Zeit ausgeführt werden.
quelle