Komplexität beim Anwenden einer Permutation an Ort und Stelle

Zu meiner Überraschung konnte ich keine Artikel zu diesem Thema finden - ich habe wahrscheinlich nach den falschen Stichwörtern gesucht.

Wir haben also eine Reihe von Dingen und eine Funktion für ihre Indizes. ist eine Permutation.$f$$f$

Wie ordnen wir das Array nach wobei Speicher und Laufzeit so nahe wie möglich an und ?$f$$O(1)$$O(n)$

Gibt es zusätzliche Bedingungen, wenn diese Aufgabe einfacher wird? Wenn wir beispielsweise explizit wissen, dass eine Funktion die Umkehrung von ?$g$$f$

Ich kenne einen Algorithmus, der Zyklen folgt und einen Zyklus für jeden Index durchläuft, um zu prüfen, ob er der kleinste in seinem Zyklus ist, aber auch hier hat er die schlechteste -Laufzeit, obwohl er sich im Durchschnitt besser zu verhalten scheint ...$O(n^2)$

Option 0: Permuting In Place (1995) von Faith E. Fich, J. Ian Munro und Patricio V. Poblete Zeit Raum.$O(n \log n)$$O( \log^{2} n )$

Option 1: Betrügen Sie, indem Sie Ihre Permutation auf eine prägnante Datenstruktur komprimieren (siehe Munro http://www.itu.dk/people/ssrao/icalp03-a.pdf) .

Option 2: Speichern Sie die Dauerwelle mit einer Prime-Cycle-Dekomposition und verwenden Sie diesen zusätzlichen Platz, um http://oeis.org/A186202 zu betrügen

Option 3: Verfolgen Sie den größten Index jedes manipulierten Zyklus. Verwenden Sie für jede Iteration den größten unsichtbaren Index, um alles in seinem Zyklus um eins zu verschieben. Wenn es auf einen angezeigten Index stößt, wird die gesamte Arbeit rückgängig gemacht, da der Zyklus bereits manipuliert wurde. Zeit, Raum.$O(n^2)$$O(\#\text{cycles} * \log n)$

Option 4: Verfolgen Sie den größten Index jedes manipulierten Zyklus, jedoch nur in Chargen mit unterschiedlichen Zykluslängen. Verwenden Sie für jede Iteration den größten unsichtbaren Index, um alles in seinem Zyklus um eins zu verschieben. Wenn es auf einen sichtbaren Index stößt, wird die gesamte Arbeit rückgängig gemacht, da der Zyklus bereits manipuliert wurde. Zeit, Leerzeichen.$O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$$O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$

Option 5: Aus demselben Papier von Munro wie Option 0, für den Zyklus von drehen, wenn der größte Index in diesem Zyklus ist. Zeit und Raum.$i = 1 .. n$$p(i)$$i$$O(n^2)$$O(\log n)$

Wenn Sie die Zyklusdarstellung der Permutation verwenden, benötigen Sie 1 zusätzliches Array-Element, um das aktuell permutierte Element zu speichern, und Sie können die Zyklen in schlechteren O (N) -Operationen durchlaufen.

Jede Permutation von N Elementen kann unter Verwendung von N-1 oder weniger Austauschen in jede andere Permutation konvertiert werden. Im schlimmsten Fall sind für diese Methode möglicherweise O (n ^ 2) -Aufrufe an Ihr Orakel F () erforderlich. Beginnen Sie von der niedrigsten Position. Sei x die Position, die wir gerade tauschen.

Wenn F (x)> = x, vertauschen Sie die Positionen x und F (x). Ansonsten müssen wir herausfinden, wo sich das Element, das sich an Position F (x) befand, derzeit in der Liste befindet. Wir können dies mit der folgenden Iteration tun. Sei y = F (x). Machen Sie, bis y> = x: y = F (y): End Do. Tauschen Sie nun die Positionen x und y aus.

Diese Methode verwendet die Umkehrung von F und erfordert n Speicherbits. Wenn x die Position eines Elements im ursprünglichen Array ist, sei G (x) die Position des Elements im sortierten Array. Sei B ein n-Bit-Array. Setzen Sie alle n Bits von B auf 0.

FOR x = 1 bis n-1: WENN B (x) == 0 DANN: y = G (x): BIS x == y: Vertausche die Positionen x und y: B (y) = 1: y = G ( y): LOOP: ENDIF: NEXT X

Bei dieser Methode wird der aktuell an Position x befindliche Artikel an die endgültige Position des Artikels verschoben. Die innere Schleife endet, wenn der richtige Gegenstand in Position x getauscht wird. Da bei jedem Tausch mindestens ein Objekt an die Endposition des Objekts verschoben wird, kann die innere Do-Schleife während des Laufs nicht mehr als n-1-mal ausgeführt werden. Ich denke, diese Methode ist O (n) Zeit und Raum.