Patience Sort

[hotti]

hi,

gegeben ist eine Sequenz mit, sagen wir, 5 Schlüsseln. Dazu gibt es eine Tabelle mit zwei Spalten: Vorgänger, Nachfolger

Die Sequenz soll nun sortiert werden, mit der Tabelle erst ergibt sich eine verkettete Liste, Patience Sort, Algorithmus:

Für jeden Schlüssel aus o.g. Sequenz, gehe in die Tabelle, gib den Schlüssel als Vorgänger aus und finde den Nachfolger; gibt dann den Schlüssel als Nachfolger aus und finde den Vorgänger (2 Abfragen). Wenn dann noch bekannt ist, mit welchem Schlüssel die Sequenz beginnen oder enden soll, kann diese Sequenz als verkettete Liste sortiert ausgegeben werden.

Geduld ist angesagt ;)

Gibt es andere Lösungen, die evntl. ein biscken flotter sind?

Hotti

[Encoder]

Mach mal ein Beispiel dazu. Ich weiß nicht ob ichs kapiert hab.

Eine einfache Idee, aus dem was ich bisher rauslese.
Kennst du die Schlüssel alle schon im Voraus? Dann lade doch alles zu ihnen auf einmal und bau dir die Sequenz mit einem Hashverfahren zusammen.
Also jeder Schlüssel zeigt auf seinen Vorgänger und Nachfolger. Du solltest jedes solche Objekt mit dem Schlüssel "greifen" können, als Hash zum Beispiel.
Dann füll anhand der Daten die Vorgänger/Nachfolger.
Danach durchläufst du die Objekte und hängst zu jedem Schlüssel aus dem Datenobjekt seinen Vorgänger und Nachfolger dran. Als Ergebnis hast du eine doppelt verkettete Liste.

[hotti]

Mach mal ein Beispiel dazu. Ich weiß nicht ob ichs kapiert hab.

Hast Du ;)

Die Lösung habe ich ja schon, genauso wie Du beschrieben hast, mache ich sowas in Perl mit prepared Statements und einer Callbackfunktion, letztere schreibt den ganzen Kram auf eine (Hash)Referenz, das ist dann die doppelt verkettete Liste.

Der Algorithmus ist klar, von Vorteil, dass er nicht rekursiv ist, von Nachteil vermutlich, dass er so langsam ist wie er heißt ;)

Vergleichbar mit Patience "Solitär": Gegeben sind ein paar Karten und ein Stoß mit Karten. Für jede Karte ist der Stoß durchzugehen um den Vorgänger und den Nachfolger für die betreffende Karte zu finden.

Vielleicht gibt es aber auch noch ne andere Lösung mit SelfJoin oder so...

Viele Grüße,
Hotti

[Encoder]

Vergleichbar mit Patience "Solitär": Gegeben sind ein paar Karten und ein Stoß mit Karten. Für jede Karte ist der Stoß durchzugehen um den Vorgänger und den Nachfolger für die betreffende Karte zu finden.

So rum gehts nicht?
Denn Stoß nur einmalig durchgehen, du weißt für welche Karte die Stoßkarte Vorgänger und Nachfolger ist, findest die anhand eines Hashs mit O(1) und weist die Karte aus dem Stoß zu.
Das wäre mein Ansatz gewesen. Damit brauchst du nicht den Stoß etliche male zu durchlaufen.

[hotti]

hi,

Das wäre mein Ansatz gewesen. Damit brauchst du nicht den Stoß etliche male zu durchlaufen.

Freilich muss ich da nur einmal durch: Es ist nur der Vergleich mit Patience Solitair, der hinkt ;)

Hotti