Frage
Implementieren Sie eine Funktion bool chainable(vector<string> v) , die eine Reihe von Strings als Parameter akzeptiert und true zurückgibt, wenn sie verkettet sein können. Zwei Strings können verkettet werden, wenn der erste mit demselben Zeichen endet, mit dem der zweite beginnt, z. B .:
Meine Lösung:
Meine Logik ist, dass es, wenn es verkettbar ist, nur einen Anfang und ein Ende gibt, die nicht übereinstimmen. Also erstelle ich eine Liste von Starts und eine Liste von Enden. wie so.
%Vor%Wenn ich die allgemeinen Elemente entferne, sollten die Listen höchstens ein Element enthalten. nämlich s und k. Wenn dies der Fall ist, ist die Liste verkettbar. Wenn die Liste zyklisch ist, sind die endgültigen Listen leer.
Aber ich denke, dass mir hier einige Fälle fehlen,
BEARBEITEN: Okay, klar, ich hatte Fehler in meiner Lösung. Können wir den besten Algorithmus dafür abschließen?
Das Problem besteht darin, zu überprüfen, ob ein Euler-Pfad in dem gerichteten Graphen existiert, dessen Scheitelpunkte die Buchstaben sind, die als erstes oder vorkommen letzter Buchstabe von mindestens einem der gelieferten Wörter und deren Kanten die gelieferten Wörter sind (jedes Wort ist die Kante vom ersten bis zum letzten Buchstaben).
Einige notwendige Bedingungen für die Existenz von Euler-Pfaden in solchen Graphen:
Die Notwendigkeit ist leicht zu sehen: Wenn ein Graph Eulersche Pfade hat, trifft jeder dieser Pfade alle Knoten außer den isolierten Knoten (weder ausgehende noch eingehende Kanten). In der hier betrachteten Grafik gibt es keine isolierten Ecken. In einem Euler-Pfad wird bei jedem Besuch eines Scheitelpunktes mit Ausnahme von Anfang und Ende eine ein- und eine ausgehende Kante verwendet, sodass jeder Scheitelpunkt mit der möglichen Ausnahme des Anfangs- und Endscheitelpunkts ebenso viele ein- und ausgehende Kanten aufweist. Der Startknoten hat eine weitere ausgehende Kante als einkommend und der Endknoten eine weitere ankommende Flanke als ausgehend, es sei denn, der Euler-Pfad ist ein Zyklus. In diesem Fall haben alle Knoten gleich viele ein- und ausgehende Kanten.
Nun ist wichtig, dass diese Bedingungen auch ausreichen . Das kann man durch Induktion über die Anzahl der Kanten nachweisen.
Dies ermöglicht eine sehr effiziente Überprüfung:
indegree - outdegree für alle Scheitelpunkte Wenn number of components > 1 oder mindestens ein Scheitelpunkt mit |indegree - outdegree| > 1 vorhanden ist oder mehr als zwei Scheitelpunkte mit indegree != outdegree vorhanden sind, sind die Wörter nicht verkettbar, andernfalls sind sie.
Ist das nicht ähnlich dem berüchtigten Problem mit dem Verkaufsmitarbeiter ?
Wenn Sie n -Zeichenfolgen haben, können Sie daraus ein Diagramm erstellen, wobei jeder Knoten einer Zeichenfolge entspricht. Sie konstruieren die Kanten folgendermaßen:
a und b verkettbar sind, führt man eine Kante a -> b mit dem Gewicht 1 ein. a und b , führen Sie eine Kante a -> b mit dem Gewicht n . Dann sind alle Ihre Ketten kettenbar (ohne Wiederholung) genau dann, wenn Sie eine optimale TSP-Route in der Grafik finden können, deren Gewicht kleiner als 2n ist.
Hinweis: Ihr Problem ist eigentlich einfacher als TSP, da Sie String Chaining immer in TSP umwandeln können, aber nicht unbedingt umgekehrt.
Hier ist ein Fall, in dem Ihr Algorithmus nicht funktioniert:
%Vor% Ihre Start- und Endlisten sind beide s, p, l, n , aber Sie können keine einzelne Kette erstellen (Sie erhalten zwei Ketten - ship->pass und lion->nail ).
Eine rekursive Suche wird wahrscheinlich am besten sein - wählen Sie ein Anfangswort (1), und versuchen Sie für jedes nachfolgende Wort (2), das kleinere Problem der Erzeugung einer Kette zu lösen, beginnend mit (2) enthält alle Wörter außer (1).
Wie Phimuemue gezeigt hat, ist dies ein Graphproblem. Sie haben eine Menge von Strings (Vertices) mit (gerichteten) Kanten. Natürlich muss die Grafik verbunden sein, um verkettbar zu sein - dies ist leicht zu überprüfen. Leider sind die Regeln darüber hinaus ein wenig unklar:
Wenn Strings mehr als einmal verwendet werden können, aber Links nicht, dann besteht das Problem darin, einen Euler-Pfad , was effizient gemacht werden kann. Ein Euler-Pfad verwendet jede Kante einmal, kann jedoch Scheitelpunkte mehr als einmal verwenden.
%Vor%Wenn die Strings nicht mehr als einmal verwendet werden, besteht das Problem darin, einen Hamilton-Pfad zu finden. Da das Hamilton-Pfad-Problem NP-vollständig ist, ist keine exakte effiziente Lösung bekannt. Natürlich ist Effizienz für kleine n nicht wirklich wichtig, und eine Brute-Force-Lösung wird gut funktionieren.
Allerdings sind die Dinge nicht ganz so einfach, weil die Menge der Graphen, die als Eingaben für dieses Problem auftreten können, begrenzt ist. Zum Beispiel ist das Folgende ein gültiges gerichtetes Diagramm (in dot Notation) (*).
%Vor% Allerdings kann dieser Graph nicht aus Strings konstruiert werden, indem man die Regeln dieses Puzzles verwendet: Da alpha und gamma beide mit beta verbunden sind, sind sie muss mit dem gleichen Zeichen enden (nehmen wir an, dass sie mit 'x' enden), aber gamma verbindet sich auch mit delta , also muss auch delta beginnen mit 'x'. Aber delta kann nicht mit 'x' beginnen, denn wenn dies der Fall wäre, dann wäre eine Kante alpha -> delta , die nicht im ursprünglichen Graphen ist.
Daher ist nicht das gleiche Problem wie das Hamilton-Pfadproblem, weil die Menge der Eingänge eingeschränkter ist. Es ist möglich, dass ein effizienter Algorithmus existiert, um das String-Ketten-Problem zu lösen, selbst wenn kein effizienter Algorithmus existiert, um das Hamilton-Pfadproblem zu lösen.
Aber ... ich weiß nicht, was dieser Algorithmus wäre. Vielleicht wird jemand anderes eine echte Lösung finden, aber in der Zwischenzeit hoffe ich, dass jemand diese Antwort interessant findet.
(*) Es hat auch einen Hamilton-Pfad: alpha -> beta -> gamma -> delta , aber das ist irrelevant für das, was folgt.
Wenn Sie petal und lion durch pawn und label ersetzen, haben Sie immer noch:
starts:s,p,l,n
ends: p,l,n,k
Ihr Algorithmus entscheidet, ob er verkettbar ist, aber das ist er nicht Das Problem besteht darin, dass Sie die ersten und letzten Buchstaben jedes Wortes trennen.
Ein rekursiver Backtracking- oder dynamischer Programmieralgorithmus sollte dieses Problem lösen.
prüfen Sie separat auf "Ist kettenfähig" und ist "zyklisch"
Wenn es zyklisch sein soll, muss es zuerst verkettbar sein. Sie könnten so etwas tun:
%Vor%Hinweis: Das ist der Fall, wenn Sie nur das erste und letzte Element der Kette auf "cylic" überprüfen.
Hier ist ein einfaches Programm, um dies iterativ zu tun:
%Vor%