Need Algorithmus zur Sequenzberechnung

Question

Ich versuche, die Lösung für ein Problem zu finden, wo ich so etwas wie

haben

1. A> B
2. B> C
3. B> D
4. C> D

Und ich soll die Antwort als A> B> C> D

Bedingungen für dieses Problem

1. Die Ausgabe wird alle Elemente beinhalten.
2. Das Problem wird keine falschen Eingaben haben. beispielsweise (A> B) (C> D) ist eine Scheineingabe, da wir die Ausgabe nicht bestimmen können.
3. Die Eingänge jeder Größe sein kann, aber nie gefälschte und es wird immer eine Lösung für das Problem sein.

Ich brauche eine Lösung für diese optimal mit Hilfe von Java Collections zu finden. Irgendwelche Tipps / Hinweise sind willkommen.

Vielen Dank im Voraus!

Answer 1

Es ist eine topologische Sortierung genannt. http://en.wikipedia.org/wiki/Topological_sorting

Da sollten Sie in der Lage sein, Ihre Hausaufgaben auf eigene Faust zu beenden.

Answer 2

Ich wette Sie vor kurzem abgedeckt Graphen in dieser Klasse ...
Wie denken Sie ein Diagramm angewendet hier werden könnte?
Können Sie sich eine Struktur, die man auf der Grundlage der Problemeingänge bauen würde (A> B> A> D, C> A etc.)? Vielleicht eine Art von Graphen ...

Sobald das Problem in einem solchen Graph ausgedrückt wird, würde bedeuten, die Lösung der Navigation der Graph ...

Answer 3

Sie beginnen, sie in einem List setzen. Die Liste wird sortiert, so dass für die nth Paar (a, b), Sie a nachzuschlagen, eine binäre Suche verwenden. Wenn es bereits überspringen vorhanden ist, Sie, wenn nicht einfügen in geeigneten Punkt in. Da a > b, tun Sie das noch einmal mit b im restlichen Teil der Liste. Hoffe, dass diese Hilfe.

Answer 4

Sie können dies tun mit einer Karte der Eingänge und einer rekursiven Methode, die es die Antwort auf eine zurück List (oder gerade druckt jeder Knoten, wie sie den Baum absteigt.) Fügt Wenn Sie die Antwort kehren dann vor , um die zurückgegebenen Liste -pending wird die Antwort von rückgängig gemacht D- verhindern> C-> B> A, wenn eine vollständige (oder Sie können nur .reverse () die Liste am Ende.) Sie zu Test nicht vergessen für eine Pause Zustand, wenn Rekursion. (Hinweis: Schlüssel nicht gefunden)