Algorithmus zum Sortieren von Zahlenpaaren

14

Ich habe diese Frage bereits beim Stackoverflow gestellt , aber vielleicht ist sie besser für diese Site geeignet.

Das Problem ist:

Ich habe N Paare von vorzeichenlosen ganzen Zahlen. Ich muss sie sortieren. Der Endvektor von Paaren sollte nicht absteigend nach der ersten Zahl in jedem Paar und nicht absteigend nach der zweiten Zahl in jedem Paar sortiert werden. Bei jedem Paar können das erste und das zweite Element zu einem beliebigen Zeitpunkt vertauscht werden. Manchmal gibt es keine Lösung, deshalb muss ich dann eine Ausnahme auslösen.

Beispiel:

in pairs:
1 5
7 1
3 8
5 6

out pairs:
1 7     <-- swapped
1 5     
6 5     <-- swapped
8 3     <-- swapped

^^ Ohne Paartausch ist es unmöglich die Lösung zu erstellen. Also tauschen wir die Paare (7, 1), (3, 8) und (5, 6) und bilden das Ergebnis. oder

in pairs:
1 5
6 9

out:
not possible

Vielen Dank

bearbeiten:

Tom Sirgedas schlug auf SO die beste Lösung vor . Es ist sehr einfach zu implementieren und funktioniert in O (log (n) * n). Vielen Dank für die Antworten und das Interesse. Ich mjqxxxx Analyse wirklich genossen.

Klark
quelle
6
Interessantes Problem. Ohne das Tauschen ist es unkompliziert, aber mit dem Tauschen ist nicht klar, dass es eine eindeutige Lösung gibt.
Dave Clarke
2
Es gibt nicht immer eine eindeutige Lösung. Dh (1, 10), (5, 6). Beide (1, 10), (5, 6) und (1, 10), (6, 5) sind korrekt.
Klark
4
Bitte fügen Sie das nächste Mal einen Link hinzu. stackoverflow.com/questions/5323941/…
Tsuyoshi Ito
2
Ein Freund von mir hat es als Test-Interview-Frage bekommen. Also ich denke, es ist nur aus Neugier :)
Klark
3
(1) Klark, vielen Dank für die Antwort. (2) Ich denke nicht, dass diese Frage eine Frage auf Forschungsebene ist, aber ich denke, dass es der Umfang ist, der geändert werden sollte. Ich habe eine Diskussion über Meta gestartet .
Tsuyoshi Ito

Antworten:

8

Angenommen, zwei Paare und sind nicht austauschbar, wenn sie in der sortierten Liste in einer beliebigen Reihenfolge platziert werden können, ohne eine der beiden auszutauschen. Dies gilt , wenn entweder ( a 1a 2b 1b 2 ) oder ( a 2a 1b 2b 1 ) . Beachten Sie, dass und genau dann nicht Swap-kompatibel sind, wenn sie mit zwei Swaps kompatibel sindp 2 = ( a 2 , b 2 ) p 1 p 2p1=(a1,b1)p2=(a2,b2)(a1a2b1b2)(a2a1b2b1)p1p2(da die Teilordnung definiert erfüllen , in denen * die Swap - Operation bezeichnet). Schließlich p 1 und p 2 sind eine-Swap - kompatibel , wenn sie mit genau einer von ihnen tauschte in beliebiger Reihenfolge in der sortierten Liste gesetzt werden. Dies trifft zu, wenn p 1 und p 2 nicht Swap-kompatibel sind. In den übrigen Fällen sind p 1 und p 2p1p2p2p1p1p2p1p2p1p2 sind einfach inkompatibel: Sie können die Bestellbedingung unabhängig von ihrem Swap-Status nicht erfüllen.

Das Problem kann nun wie folgt gelöst werden. Testen Sie jedes Paar. Wenn ein Paar nicht kompatibel ist, gibt es keine Lösung und wir können eine Ausnahme auslösen. Betrachten Sie andernfalls das Diagramm mit Knoten, die den ursprünglichen Paaren entsprechen, und Kanten zwischen den Knotenpaaren, die nicht mit einem Swap kompatibel sind. Jedes derartige Knotenpaar muss in einer ordnungsgemäß sortierten Liste den gleichen Auslagerungsstatus haben, und daher müssen alle Knoten in jeder verbundenen Komponente des Diagramms den gleichen Auslagerungsstatus haben. Wir müssen feststellen, ob diese komponentenweiten Auslagerungszustände konsistent zugewiesen werden können. Testen Sie alle Knotenpaare in jeder verbundenen Komponente. Wenn ein Paar nicht No-Swap-kompatibel ist, gibt es keine Lösung, und wir können eine Ausnahme auslösen. Testen Sie nun alle verbundenen Komponentenpaare (dh für die Komponenten C1und , testet alle Paare von Knoten p 1C 1 und p 2C 2 ). Wir wissen, dass jedes Komponentenpaar mindestens One-Swap-kompatibel ist, aber einige Paare können auch No-Swap-kompatibel sein (da jedes Knotenpaar, das nicht durch eine Kante verbunden ist, mindestens One-Swap-kompatibel ist und auch No-Swap-kompatibel sein kann). Swap-kompatibel). Betrachten Sie einen reduzierten Graphen mit Knoten, die den verbundenen Komponenten entsprechen, und eine Kante zwischen zwei Knoten, wenn die entsprechenden Komponenten nicht No-Swap-kompatibel sind. Es gibt eine Lösung für das ursprüngliche Problem, wenn dieses Diagramm 2- farbig ist. Wenn es keine 2 gibtC2p1C1p2C222-Farben gibt es keine Lösung, und wir können eine Ausnahme auslösen. Wenn es einen gibt, tauschen Sie alle Knoten in allen Komponenten einer Farbe aus. Wir haben jetzt die Garantie, dass zwei beliebige Knoten No-Swap-kompatibel sind, und können die Liste der Paare anhand der definierten Teilreihenfolge ordnungsgemäß sortieren.

Jeder Schritt im Algorithmus und damit der gesamte Algorithmus kann in -Zeit ausgeführt werden.O(N2)


UPDATE: Eine viel elegantere Konstruktion ist die folgende. Wenn ein Paar von Paaren nicht No-Swap-kompatibel ist, verbinden Sie die entsprechenden Knoten mit einer Kante (zwingen Sie sie, unterschiedliche Farben in einer beliebigen Zweifarbigkeit zu haben). Wenn ein Paar von Paaren nicht mit einem Tausch kompatibel ist, verbinden Sie die entsprechenden Knoten mit einer Kette der Länge 2 (wobei erzwungen wird, dass sie in jeder Zweifarbigkeit dieselbe Farbe haben). Es gibt nur dann eine Lösung, wenn das resultierende Diagramm zweifarbig ist. Um eine Lösung aus einer blau-roten Färbung des Diagramms zu erstellen, tauschen Sie nur die Paare aus, deren entsprechende Knoten blau sind, und sortieren Sie dann die resultierende Liste.

mjqxxxx
quelle
1
Vielen Dank für Ihre Antwort. Ich habe es wirklich genossen, es zu lesen. Überprüfen Sie die auf SO vorgeschlagene Antwort. Obwohl es nicht auf der Graphentheorie beruht, was bedeutet, dass es weniger interessant ist als Ihre elegante Lösung :), ist es schneller. Vielen Dank für Ihre Zeit.
Klark
3

Es sei X (a, b) die binäre Variable, die angibt, ob das Paar (a, b) ausgetauscht werden soll. Betrachten Sie ein Paar unterschiedlicher Paare (a, b) und (c, d) und schreiben Sie eine binäre Bedingung für die Variablen X (a, b) und X (c, d), die genau dann erfüllt ist, wenn die beiden Paare in sind die richtige Reihenfolge nach dem Durchführen der durch X (a, b) bzw. X (c, d) angegebenen Swaps. Die Konjunktion all dieser binären Bedingungen ist eine 2-SAT-Formel in n Variablen und O (n ^ 2) -Klauseln, die genau dann erfüllt werden kann, wenn das ursprüngliche Problem eine Lösung hat. Dies kann in der Zeit O (n ^ 2) überprüft werden.


Beachten Sie, dass für die ursprüngliche Lösung alle Bedingungen die Form X (a, b) = X (c, d) oder X (a, b) haben! = X (c, d) (oder X (a, b) = Konstante), so funktioniert ein einfacher Algorithmus "Zusammenführen und auf Zweiteiligkeit prüfen":

Beginnen Sie damit, dass jedes X für die Menge steht, die nur sich selbst enthält. dann füge für jedes Paar (X, Y), so dass X = Y eine Beschränkung ist, die Komponenten zusammen, zu denen X und Y gehören; und prüfen Sie schließlich, ob der zusammengezogene Graph, bei dem jede Komponente ein Eckpunkt und eine Kante die Komponenten mit X und Y verbindet, zweigeteilt ist, wenn die Beziehung X! = Y gelten muss.

David
quelle
1
X(ein,b)=X(c,d)
So? Die Äquivalenzrelation ist hier der transitive Abschluss der Beziehung (a, b) R (c, d) iff a c und b d oder umgekehrt. Vielleicht war ich nicht ganz explizit, aber das sollte aus meiner Antwort hervorgehen.
David
1
ein<cb>dX(ein,b)X(c,d)(1,10)(2,5)(3,7)
1
XY.X¬Y.
1
Machst du Witze? Zunächst kann jede Beziehung zwischen nur zwei Variablen als 2-SAT-Formel ausgedrückt werden. Zum Beispiel ist X = Y dasselbe wie (X impliziert Y) und (nicht X impliziert nicht Y). Wenn jedoch alle Bedingungen tatsächlich die Form X = Y oder X = nicht Y haben, muss der 2SAT-Algorithmus überhaupt nicht ausgeführt werden: Der einfachere Algorithmus zum Zusammenführen und Überprüfen auf Zweiteiligkeit, den ich zuvor beschrieben habe, funktioniert.
David