Riffle-Shuffle-Algorithmus für lineare Zeit an Ort und Stelle

15

Gibt es einen linearen Time-In-Place-Riffle-Shuffle-Algorithmus? Dies ist der Algorithmus, den einige besonders geschickte Hände ausführen können: Ein Eingangsarray mit gerader Größe wird gleichmäßig aufgeteilt und die Elemente der beiden Hälften werden verschachtelt.

Mathworld hat eine kurze Seite über Riffle Shuffle . Insbesondere interessiert mich die Out-Shuffle-Variante, mit der das Eingangsarray 1 2 3 4 5 6 in 1 4 2 5 3 6 umgewandelt wird. Beachten Sie, dass die Eingangslänge in ihrer Definition beträgt 2n.

Es ist unkompliziert, dies in linearer Zeit durchzuführen, wenn wir ein zweites Array mit der Größe n oder mehr zur Hand haben. Kopieren Sie zuerst die letzten n Elemente in das Array. Dann, unter der Annahme , 0 basierte Indizierung, kopiert die ersten n Elemente aus Indizes [0,1,2,...,n1] auf [0,2,4,...,2n2] . Dann kopieren Sie die nElemente aus der zweiten Anordnung zurück zu der Eingangsanordnung, Abbilden Indizes [0,1,2,...,n1] auf [1,3,5,...,2n1] . (Wir können etwas weniger arbeiten, da das erste und das letzte Element in der Eingabe nicht verschoben werden.)

Eine Möglichkeit, dies an Ort und Stelle zu versuchen, besteht darin, die Permutation in disjunkte Zyklen zu zerlegen und die Elemente dann nach jedem Zyklus neu anzuordnen. Unter der Annahme einer 0-basierten Indizierung ist die Permutation im 6-Element-Fall wieder

σ=(012345024135)=(0)(5)(1243).

Wie erwartet sind das erste und das letzte Element feste Punkte, und wenn wir die mittleren 4 Elemente permutieren, erhalten wir das erwartete Ergebnis.

Leider ist mein Verständnis der Mathematik der Permutationen (und deren ) basiert hauptsächlich auf Wikipedia, und ich weiß nicht, ob dies in linearer Zeit möglich ist. Vielleicht können die mit diesem Mischen verbundenen Permutationen schnell aufgelöst werden? Außerdem brauchen wir nicht einmal die vollständige Zerlegung. Nur ein einzelnes Element aus jedem der disjunkten Zyklen zu bestimmen, würde ausreichen, da wir den Zyklus aus einem seiner Elemente rekonstruieren können. Möglicherweise ist ein völlig anderer Ansatz erforderlich.LATEX

Gute Ressourcen zur verwandten Mathematik sind ebenso wertvoll wie ein Algorithmus. Vielen Dank!

Johny
quelle
Es gibt eine -Zeitlösung (mit O ( 1 ) zusätzlichem Raum). Ich kenne keine zeitlineare Lösung. O(nlgn)O(1)
Radu GRIGore
4
Das ist besser für cs.stackexchange geeignet. Im ungleichmäßigen Modell ist immer eine -Zahl möglich. In diesem Fall sollte es sogar gleichmäßig möglich sein. O(n)
Yuval Filmus
1
@Radu Ähnlich wie bei dieser Frage gibt es für dieses Problem wahrscheinlich keine Lösung, bei der nur zusätzlicher Speicherplatz, sondern O ( log n ) zusätzlicher Speicherplatz verwendet wird. O(1)O(logn)
Tyson Williams
2
Ich nehme meinen Kommentar (und stimme ab, um ihn zu schließen) zurück! (Obwohl die Frage in der Literatur beantwortet wird.)
Yuval Filmus
1
Ich habe diese Frage letzte Woche von einem CS-Studenten gehört, der sie bei einem Vorstellungsgespräch gehört hat.
Jeffs

Antworten:

12

Das Problem ist überraschend nicht trivial. Hier ist eine schöne Lösung von Ellis und Markov, In-Situ, Stabiles Zusammenführen mittels Perfect Shuffle (Abschnitt 7). Ellis, Krahn und Fan, Computing the Cycles in the Perfect Shuffle Permutation , schaffen es, "Cycle Leader" auf Kosten von mehr Speicher auszuwählen. Ebenfalls verwandt ist das schöne Paper von Fich, Munro und Poblete, Permuting In Place , das einen allgemeinen -Zeitalgorithmus für das Orakelmodell liefert . Wenn nur ein Orakel für die Permutation verfügbar ist, benötigt der Algorithmus logarithmischen Speicherplatz. Wenn wir auch ein Orakel für das Inverse haben, benötigt es konstanten Raum.O(nlogn)

Nun zu Ellis und Markovs Lösung. Nehmen wir zunächst . Dann wird die Berechnung der perfekten Mischung der Ordnungen n auf die Berechnung der perfekten Mischung der Ordnungen x und y mit einer Rotation vor ihnen reduziert . Hier ist ein Beweis durch Beispiel ( n = 5 , x = 3 , y = 2 ): 012 345 67 89 012 567 34 89 051627 3849n=x+ynxyn=5x=3y=2

012345678901256734890516273849

Ellis und Markov fanden einen einfachen Weg, um die perfekte Verschiebung zu berechnen, wenn , und zwar unter Verwendung von konstantem Raum und linearer Zeit. Damit erhalten wir einen Algorithmus zur Berechnung des perfekten Shuffle für beliebiges n . Schreiben Sie zunächst n = 2 k 0 + + 2 k w unter Verwendung der binären Codierung von n und lassen Sie n i = 2 k i + + 2 k w . Drehe die mittleren n 0 Bits, mische die rechten 2 kn=2knn=2k0++2kwnni=2ki++2kwn0 Bits. Ignorieren Sie die rechten2 k 0 Bits, drehen Sie die mittlerenn1Bits und mischen Sie die rechten2 k 1 Bits. Und so weiter. Beachten Sie, dass die Drehung einfach ist, da die ersten gedrehten Elemente als Zyklusleiter fungieren. Die Gesamtkomplexität der Rotation istO(n0++nw)=O(n), dan t + 1 <nt/2. Die Gesamtkomplexität der inneren Mischen istO(2k02k0n12k1O(n0++nw)=O(n)nt+1<nt/2 .O(2k0++2kw)=O(n)

Es bleibt zu zeigen, wie der perfekte Shuffle berechnet wird, wenn . In der Tat werden wir in der Lage sein, nach klassischer Arbeit an Halsketten Fahrradführer zu identifizieren (Fredricksen und Maiorana, Halsketten aus Perlen in k Farben und k -ary de Bruijn Sequenzen ; Fredricksen und Kessler, Ein Algorithmus zur Erzeugung von Halsketten aus Perlen in zwei Farben ).n=2kkk

Was ist die Verbindung? Ich behaupte, dass die Shuffle-Permutation einer Verschiebung der Binärdarstellung nach rechts entspricht. Hier ist ein beispielhafter Beweis für : 000 001 010 011 100 101 110 111 000 100 001 101 010 110 011 111 Um Zyklusleiter zu finden, müssen wir aus jeder Äquivalenzklasse der Rotation von einen Vertreter finden binäre Zeichenfolgen der Länge k . Die oben erwähnten Arbeiten geben den folgenden Algorithmus zum Erzeugen aller Zyklusleiter an. Beginnen Sie mit 0 kn=8

000001010011100101110111000100001101010110011111
k0k. Bei jedem Schritt sind wir irgendwann . Finden den maximalen Index i von einem Null - Bit, divide k von i zu erhalten , k = d i + r , und lassen Sie die folgende Nummer sein ( ein 1 ... a i - 1 1 ) d ein 1 ... eine r . Immer wenn r = 0 ist , ist der neue String ein Cycle Leader.a1akikik=di+r(a1ai11)da1arr=0

Wenn beispielsweise wird die Sequenz 0000 , 0001 , 0010 , 0011 , 0101 , 0110 , 0111 , 1111 generiert .n=16

0000,0001,0010,0011,0101,0110,0111,1111.

Die Fahrradführer sind hervorgehoben.

Yuval Filmus
quelle
3
2323k30,,3k
Obwohl ich denke, dass Jains Artikel etwas einfacher ist, bevorzuge ich den früheren Artikel sowie den früheren Beitrag mit den meisten Stimmen.
Johny
6

Dies war eine Seeding-Frage bei cs.stackexchange.com und eine Antwort finden Sie hier: /cs/332/in-place-algorithm-for-interleaving-an-array/400#400

Es ist eine Erklärung des Papiers: http://arxiv.org/abs/0805.1598 .

k2k32k=2

j2jmod2n+1

Aryabhata
quelle
Ha! Ich habe diese Frage völlig vergessen, auch wenn ich an der Diskussion teilgenommen habe. Das heißt, ich habe damals nicht wirklich verstanden, wie es funktioniert.
Radu GRIGore
2

mn=m2if(i)=2iin/2f(i)=2(imodn/2)1i>n/2

O(1)O(logn)

Robert Robere
quelle
Ah, warte. Dies setzt voraus, dass alle Werte in der Riffelpermutation auf demselben Zyklus liegen. Diese Strategie müsste ein wenig geändert werden, je nachdem, wie viele disjunkte Zyklen es gibt.
Robert Robere