längste Liste von Wörtern mit übereinstimmenden Start- und Endbuchstaben

Mein Freund gab mir ein Problem, von dem er sagt, dass es einfach ist, aber ich kann keinen guten Algorithmus finden, um es zu tun.

Sie erhalten eine Eingabe von 100 zufälligen englischen Wörtern. Sie müssen die längste Wortfolge finden, bei der der letzte Buchstabe in einem Wort mit dem ersten Buchstaben im nächsten Wort übereinstimmt. Sie können jedes Wort nur einmal verwenden.

Wenn Sie beispielsweise die Wörter "Katze", "Hund", "das" erhalten würden, wäre die längste Zeichenfolge, die Sie erstellen könnten, "Katze -> das". Wenn Sie die Wörter "Maus", "Elch", "Einhorn" erhalten würden, wäre die längste Zeichenfolge, die Sie erstellen könnten, nur ein Wort (da keines dieser Wörter verknüpft ist). Wenn Sie die Wörter "Vogel", "Gericht", "Hafen" erhalten würden, wäre die längste Schnur, die Sie machen könnten, "Hafen -> Vogel -> Gericht" (oder "Gericht -> Hafen -> Vogel" oder "Vogel -"). > Gericht -> Hafen ").

Ich hatte die Idee, dies als gerichteten zyklischen Graphen zu modellieren. Jeder Knoten wäre nur ein Wort, wobei Scheitelpunkte zu jedem Wort / Knoten gehen, das mit dem Buchstaben begann, mit dem dieses Wort endete.

+-------+         \ +------+
|  cat  |-----------| that |
+-------+         / +------+
    |                  |
   \|/                 |
+-------+ /            |
|  the  |--------------+
+-------+ \

Dieses Problem scheint eine Suche nach dem längsten Pfad zu sein , nämlich NP-Hard.

Gibt es einen besseren Weg, dies zu tun? Oder sogar eine Art Approximationsalgorithmus, der verwendet werden könnte? Oder eine Möglichkeit, die Qualitäten des Englischen zu nutzen, um den Suchraum zu verkleinern?

Ich denke, dies hängt mit dem von Ihnen erwähnten LP-Problem (Longest Path) zusammen, aber es ist etwas anders. Der Hauptunterschied besteht darin, dass das LP-Problem einen höheren Grad an Konnektivität aufweist als das von Ihnen vorgeschlagene Problem. Indem Sie Ihre Verbindungen auf den letzten und den ersten Buchstaben beschränken, entfernen Sie eine große Anzahl möglicher Kombinationen.

Hier ist, wie ich empfehlen würde, dieses Problem anzugehen:

1. Zählen Sie für jedes Wort in der Liste die möglichen Ein- und Ausgänge.
2. Verwerfen Sie alle Wörter mit 0 Ein- und 0 Ausgängen.
3. Identifizieren Sie einen anfänglichen Satz von "Starterwörtern" mit der niedrigsten Anzahl von Ein- und Ausgängen, und die Ausgänge müssen größer als 0 sein.
4. Jedes Starterwort erhält eine eigene Arbeitskopie der Anzahl der Ein- / Ausgänge. Dies bildet den Kopf der Kette.
5. Identifizieren Sie für jede Kette eine Liste der "nächsten Wörter" basierend auf:
   
   • letzter Buchstabe des Starters oder vorheriges Wort
   • niedrigste Anzahl von Ein- und Ausgängen (wiederum müssen die Ausgänge größer als 0 sein)
6. next wordWiederholen Sie jeweils Schritt 5, bis die Kette endet.

Denk daran, dass:

• Sie müssen die Länge der Ketten verfolgen und über einen globalen Mechanismus verfügen, um die längste Kette zu identifizieren.

• Sie müssen auch jedes Wort aus der Arbeitskopie der Verbindungsanzahl entfernen, um eine rekursive Schleife zu vermeiden.

• Irgendwann endet Ihre Kette und Sie müssen ein Wort mit einer Anzahl von 0 Verbindungsausgängen auswählen.

• Möglicherweise müssen Sie Ins / Outs neu berechnen, wenn Wörter aus den Arbeitslisten entfernt werden. Auf den ersten Blick denke ich nicht, dass dies notwendig sein wird, da die Gesamtsätze relativ klein sein werden. Wenn Sie auf 1000 Wörter skaliert haben, kann die Konvergenz des Algorithmus durch statische Zählungen verlangsamt werden.

Ich habe das als Verpackungsproblem gesehen. Für mich identifizieren die Ein- und Ausgänge die zu verpackende Form. Je niedriger die Verbindungen, desto seltsamer die Form. Je seltsamer die Form, desto eher möchte ich sie packen, da ich bemerkte, dass die Wahrscheinlichkeit, eine seltsame Form packen zu können, abnimmt, je später ich in die Kette kam.

Als Beispiel:

{dog, gopher, alpha, cube, elegant, this, that, bart}

dog     0, 1
gopher  1, 0
alpha   0, 0
cube    0, 1
elegant 1, 2
this    3, 0
that    2, 1
bart    0, 2

//alpha is dropped with 0 in and 0 out.
//two candidates found: dog, cube

//chain 1
dog => gopher
//chain 2
cube => elegant => that => this

//Note 1: the following chain won't occur due to selection rules
//that takes priority over this because of output count
cube => elegant => this

//Note 2: this chain won't occur either due to selection rules
bart => that => this

Wenn Sie eine 26X26-Matrix erstellen, um einen gerichteten Scheitelpunktgraphen als jedes Alphabet und Wörter als Kante darzustellen. Beispiel: Wort - APPLE Verbinden Sie den Scheitelpunkt A und E mit der von A nach E gerichteten Kante. Das Problem reduziert sich nun darauf, den größten Eulerschen Pfad (Pfad, der die maximale Anzahl von Kanten enthält und jede Kante einmal mit einer möglichen Wiederholung von Scheitelpunkten besucht) im Diagramm zu finden. Einer der O (E) -Algorithmen wäre, zufällig von einem Paar von Eckpunkten aus zu beginnen. Finde einen Weg zwischen ihnen. Dann entspanne den Weg weiter, bis es möglich ist.

update @ GlenH7 Ich habe kürzlich eine ähnliche Frage auf www.hackerearth / jda gelöst. Es gab relative Noten in Bezug auf die beste Lösung und ich habe die höchsten Noten mit dem folgenden Ansatz erzielt:

Gegebene Liste von Wörtern. Finden Sie die längste Kette, die von ihnen gebildet werden kann. Eine Kette ist gültig, wenn jedes Wort mit einem Buchstaben * beginnt, der am Ende des letzten Wortes endet.

Ansatz =

1) Machen Sie den Graphen von Alphabeten als Eckpunkte und Wörter als Kanten. Verwenden Sie anstelle der Verwendung mehrerer Kanten eine mit einem Gewicht, das der Anzahl der Kanten entspricht.

2) Finden Sie die stark verbundene Komponente des Graphen mit den maximalen Kanten. Andere Kanten vorübergehend verwerfen.

3) Machen Sie für jeden Scheitelpunkt seinen Grad gleich seinem Außengrad.

4) Nun existiert ihre Eulerschaltung in der Grafik. Finde es.

5) Finden Sie nun im verbleibenden Diagramm (im Originaldiagramm den längsten Pfad mit dem ersten Scheitelpunkt in der ausgewählten stark verbundenen Komponente. Ich denke, dies ist NP-schwer.

6) Nehmen Sie die obige Spur in die Elersche Schaltung auf und wandeln Sie die Eulersche Schaltung in eine Spur um.

Warum - ich akzeptiere, dass diese Frage höchstwahrscheinlich NP-schwer ist (Vermutung, nicht mathematisch gesprochen). Der obige Ansatz funktioniert jedoch am besten, wenn es eine lange Liste (1000+) gleichmäßig verteilter Wörter gibt (dh nicht als wc für den obigen Ansatz gedacht). Nehmen wir an, dass es sich nach der Konvertierung der angegebenen Liste in ein oben genanntes Diagramm glücklicherweise um ein Euler-Diagramm handelt ( Bedingungen siehe http://en.wikipedia.org/wiki/Eulerian_path ). Dann können wir diese Antwort ohne Zweifel sagen Die obige Frage ist P und ist tatsächlich der eulersche Pfad in der Grafik (siehe http://www.graph-magics.com/articles/euler.php für eine sehr einfache Vorgehensweise, um dies zu überprüfen und zu überprüfen, ob Ihre Grafik vorhanden ist Single http://www.geeksforgeeks.org/strongly-connected-components/und wenn nicht vorübergehend andere kleine scc bereinigen, da der eulersche Pfad für einzelne scc existiert). Daher versuche ich für nicht glückliche Fälle (die fast alle Fälle sind), sie in glückliche Fälle umzuwandeln (dh die Eulersche Spurbedingung ist erfüllt). Wie macht man das? Ich habe versucht, die Suche nach irrelevanten Kanten mit zunehmender Tiefe durchzuführen (die Menge der Kanten in einem Pfad, der vom Scheitelpunkt mit einem Grad größer als Grad starrt und am Scheitelpunkt mit einem Grad größer als Grad endet). Zunehmende Tiefensuche bedeutet, dass ich zuerst nach allen solchen Sätzen einer Kante im Pfad als nach zwei Kanten im Pfad usw. gesucht habe. Auf den ersten Blick mag es so aussehen, als würde die i-te Tiefensuche O (Knoten ^ i) und damit die Gesamtzeitkomplexität von O (Knoten + Knoten ^ 2 + Knoten ^ 3 + ....) dauern, bis es ein glücklicher Fall ist. Eine amortisierte Analyse zeigt jedoch, dass es sich um O (Kanten) handelt. Sobald es reduziert ist, finden Sie Glücksfall Eulersche Schaltung.

Bis hierher war alles Polynomzeit. Dies würde fast die beste Lösung ergeben. Um Ihre Lösung weiter zu verbessern (perfekte Lösung ist NP-schwer), versuchen Sie einen gierigen Ansatz im verbleibenden Diagramm, um einen langen Pfad zu finden, der mit einem der Eckpunkte im ausgewählten scc starrt. Fügen Sie dies nun zu dem oben gefundenen Euler-Pfad hinzu, um ihn weiter zu erhöhen.

Idee:

Erstellen Sie zunächst zwei Karten (Hashes), z. B. S und E, von Buchstaben zu Wörtern. Das erste, S, ordnet Anfangsbuchstaben Wörtern zu, das zweite, E, macht dasselbe mit Endbuchstaben.

ZB wenn das Wörterbuch besteht aus:

Vogel, Teller, Hund, Hafen

wir haben:

S:

a -> [ ]
b -> [ bird ]
c -> [ ]
d -> [ dish, dog ]
...
h -> [ harb ]
...

und,

E:

a -> [ ]
b -> [ harb ]
c -> [ ]
d -> [ bird ]
...
g -> [ dog ]
h -> [ dish ]
...

Erstellen Sie als Nächstes mit S und E eine schnelle Gesamtstruktur (Baumgruppe) mit der gleichen Größe wie das Wörterbuch, mit Wurzeln an jedem Wort, und lassen Sie nicht zu, dass ein Wort mehr als einmal in einem Baum vorkommt Die Tiefen der Bäume, während Sie sie bauen:

bird (depth: 2)
   dish
      harb
   dog

dish (depth: 3)
   harb
      bird
         dog

dog (depth: 0)

harb (depth: 2)
   bird
      dish
      dog

Schließlich iterieren Sie über den Wald und finden Sie die Bäume mit der größten Tiefe.

Die Lösung (en) befinden sich auf der Nachkommenachse dieser Bäume.

Z.B,

dish / harb / bird / dog

über.