Pfadrekonstruktion mit Hashing?

Question

Ich habe versucht, herauszufinden, wie ein O (n) Zeit Komplexität Algorithmus zu finden, den folgenden in Java zu lösen:

Wir gegeben sind ein Eingangspaar mit einem Startpunkt und Endpunkt, und wir Konstrukt muss einen Pfad, so daß der Beginn eines Eingang das Ende einer anderen Eingabe übereinstimmt (in diesem Fall alphabetisch)

EX: wenn ich eine Liste

PB
BM
OPhabe MZ

wo PB oder BM-Paare sind, P der Startpunkt und B ist das Ende

wobei I sollte

OP
PB
BM
als Ausgabe erstellen MZ

Und natürlich möchte ich um nach Zyklen zu suchen - in diesem Fall werde ich nur berichten, ob es einen Zyklus gibt.

Das erste Mal, als ich das versuchte, benutzte ich einen Swapping-Algorithmus, der O (N^2) war, indem ich im Grunde genommen zwei Einträge vertauschte und die Liste nach unten bewegte. Es gibt definitiv einen schnelleren Weg, dies zu tun, und ich verstehe semi-intuitiv, wie es geht, aber ich frage mich, ob jemand es etwas aufklären könnte.

Grundsätzlich gehe ich davon aus, dass Sie eine Art Hash/Key-Struktur erstellen müssen, in der Sie den Wert des Objekts selbst mit einem Schlüssel referenzieren können.

Zum Beispiel würden Sie zwei Sammlungen behalten, eine der Starts und eine der Enden. Sie können jede Eingabe verwenden und ein Objekt mit einem Start- und einem Endfeld erstellen und dann alle Start- und Endpunkte zu zwei Arrays hinzufügen. Dann müsste man für jeden Start grundsätzlich [start] finden und nach dem Auffinden das entsprechende Objekt zu einer Liste hinzufügen.

Meine einzige Sache ist, ich kann nicht genau herausfinden, wie man das in Java unter Verwendung einer Hash-Tabelle oder einer ähnlichen Datenstruktur implementiert. Muss ich die Start- und Endpunkte zu separaten Hash-Tabellen hinzufügen und dann die Startpunkte als Suchschlüssel verwenden?

Pseudocode an jemanden aus der Suche, die es in Python auf Github gelöst:

for inputs 
    parse input 
    add parse[1] to starts, add parse[2] to ends 

for starts 
    find origin (a start not in ends) <--requires hash? 

if no origin 
    cycle exists 

for inputs 
    find ends[origin] <--requires hash? 
    origin = ends[origin] <-- so we can find the next one 

fragt sich, ob jemand mir dies in Java zu einem Algorithmus übersetzen helfen könnte (andere effiziente Lösungen sehr willkommen, da ich daran interessiert bin Art der Problemlösung) oder allgemein aus Sicht der Datenstrukturen.

Answer 1

Hier ist eine einfache Implementierung HashMaps in Java unter Verwendung von:

String[][] paths = { 
     {"P", "B"}, 
     {"B", "M"}, 
     {"O", "P"}, 
     {"M", "Z"}, 
    }; 

    // create a single hash map, mapping start->end 
    HashMap<String, String> end = new HashMap<>(); 

    for(int i = 0; i < paths.length; i++) 
    { 
     end.put(paths[i][0], paths[i][1]); 
    } 

    // find if a cycle exists 
    String origin = null; 
    for (String key : end.keySet()) { 
     if(!end.containsValue(key)) 
     { 
      origin = key; 
      break; 
     } 
    } 

    if(origin == null) 
    { 
     System.out.println("cycle exists"); 
     return; // no origin found, cycle exists 
    } 

    // iterate over hash map: 
    int count = 0; 
    while(true) 
    { 
     if(!end.containsKey(origin)) 
      break; 
     String next = end.get(origin); 
     System.out.println(origin + " " + next); 
     origin = next; 
     if(++count > paths.length) 
     { 
      System.out.println("cycle exists"); 
      break; 
     } 
    } 

end speichert den Endpunkt (Wert) angesichts der Startpunkt (Taste).

Wenn ein Punkt als Startpunkt, aber nicht als Endpunkt existiert, ist dies ein Schlüssel in end, aber kein Wert in end. Wenn Sie also über den keySet von end iterieren und prüfen, ob end jeden Schlüssel als Wert enthält, finden Sie einen Ursprung. Wenn es keinen solchen Ursprung gibt, dann gibt es einen Zyklus. Dies ist jedoch nicht ausreichend, um zu bestimmen, ob ein Zyklus vorliegt, weil es selbst bei einem Ursprung einen Zyklus geben kann. Betrachten Sie diesen Satz:

P B 
B M 
O P 
M Z 
Z M 

Es ist ein einzigartiger Ursprung (O), aber es ist auch ein Zyklus M -> Z -> M. Um dies zu erkennen Sie den Satz gehen können und zu verfolgen, die Sie bereits haben Punkt besucht, oder einfacher können Sie das Set laufen und wenn Sie mehr Punkte als die Länge der Eingabe besuchen, dann muss es einen Zyklus geben.

Um das Set zu gehen, legen Sie einen String zum Ursprung fest. Dann suchen Sie weiter nach dem Wert end gegeben origin als Schlüssel, und drucken Sie das Schlüssel, Wert-Paar (Ursprung, end.get (Ursprung)) als Anfang, Ende. Setzen Sie dann end.get (Ursprung) als neuen Ursprung. Die Schleife wird beendet, wenn in der End-HashMap für den aktuellen Ursprung kein Wert gefunden wird.

Dieser Algorithmus schlägt fehl, wenn es doppelt Start- oder Endpositionen in der Liste steht, z:

P B 
B M 
O P 
M Z 
B Z 

Es ist nicht von der Frage klar, wenn Sie diesen Fall zu behandeln haben.

Answer 2

Obwohl ich würde es vorziehen, eine verknüpfte Liste artige Struktur mit so etwas wie

class Node { 
    String name; 
    Node prev; 
    Node next; 
} 

Konstruktion es noch möglich ist, es mit Karte zu tun (HashMap wenn Sie möchten) nur.

Es auf die Antwort von @samgak ähnlich sieht, nur mit ein paar Tricks, die Ihr Code sieht kürzer machen kann (nicht notwendig schneller, haben gebenchmarkt es nicht):

String[][] rawPaths = { 
    {"P", "B"}, 
    {"B", "M"}, 
    {"O", "P"}, 
    {"M", "Z"}, 
}; 


// 1. You can keep only one `Map<String, String> which keeps start as key and end as value. 

Map<String, String> pathMap = new HashMap<>(); 
for (String[] path : rawPaths) { 
    pathMap.put(path[0], path[1]); 
} 

// 2. Some validity checks for data: 

// 2.1 No of entry in final Map should equals to number of lines in raw data, which means there is no duplicated "start" node. 
assert pathMap.size() == rawPaths.length; 

// 2.2 There should be no duplicate in "end", i.e. no partial cyclic path 
assert new HashSet<>(pathMap.values()).size() == rawPaths.length; 

// 2.3 there should be one and only one start value that does not exists in end values, i.e. no full cyclic path 
Set<String> startPoints = new HashSet<>(pathMap.keySet()); 
startPoints.removeAll(pathMap.values()); 

assert startPoints.size() == 1; 

//3. Then you can make up the path by getting the "head" which is the only value left in startPoints, and construct the full path 

String start= startPoints.iterator().next(); 

while (pathMap.contains(start)) { 
    String end = pathMap.get(start); 
    System.out.println(start + " " + end); 
    start = end; 
} 

Fällen kann es nach wie vor, dass gibt es zyklische Insel Pfad wie folgt aus:

A B 
B C 
C D 
X Y 
Y X 

, die leicht von überprüft werden kann, nachdem Sie durch 3 Teil durchquert, einen Zähler halten, und der Zähler sollte schließlich das gleiche wie pathMap.size() sein. Wenn nicht, gibt es eine zyklische Insel