Ist es möglich, ein Array mit konstantem zusätzlichen Platz umzukehren?

Question

Lassen Sie uns sagen, dass ich ein Array haben A mit n einzigartige Elemente auf dem Bereich [0, n). Mit anderen Worten, ich habe eine Permutation der ganzen Zahlen [0, n].

Ist möglich A in B zu transformieren OS unter Verwendung von (1) zusätzlichem Raum (AKA in-place), so dass B [A [i]] = i?

Zum Beispiel:

 A     B 
[3, 1, 0, 2, 4] -> [2, 1, 3, 0, 4] 

Answer 1

Ja, es ist möglich, mit O (n^2) Algorithmus:

Nimm Element bei Index 0, schreibt dann 0 in der Zelle durch dieses Element indiziert . Verwenden Sie dann das gerade überschriebene Element, um den nächsten Index zu erhalten und den vorherigen Index dort zu schreiben. Fahren Sie fort, bis Sie zum Index 0 zurückkehren. Dies ist der Zyklus-Leader-Algorithmus.

Dann tun Sie das gleiche, beginnend mit Index 1, 2, ... Aber bevor Sie irgendwelche Änderungen vornehmen, führen Sie den Zyklusleiteralgorithmus ohne irgendwelche Änderungen aus, ausgehend von diesem Index. Wenn dieser Zyklus einen Index unter dem Startindex enthält, überspringen Sie ihn einfach.

---

Oder diese O (n^3) Algorithmus:

Nimm Element bei Index 0 ist, dann 0 durch dieses Element indiziert in die Zelle schreiben. Verwenden Sie dann das gerade überschriebene Element, um den nächsten Index zu erhalten und den vorherigen Index dort zu schreiben. Fahren Sie fort, bis Sie zu Index 0 zurückgehen.

Dann machen Sie das gleiche, beginnend mit Index 1, 2, ... Aber bevor Sie Änderungen vornehmen, führen Sie den Zyklusleiter-Algorithmus ohne irgendwelche Modifikationen ausgehend von allen vorhergehenden Indizes aus. Wenn der aktuelle Index in einem vorhergehenden Zyklus vorhanden ist, überspringen Sie ihn einfach.

---

I geschrieben (leicht optimiert) implementation von O (n^2) Algorithmus in C++ 11, um zu bestimmen, wie viele zusätzliche Zugriffe für jedes Element im Mittel benötigt werden, wenn zufällige Permutation invertiert wird. Hier sind die Ergebnisse:

size accesses 
2^10 2.76172 
2^12 4.77271 
2^14 6.36212 
2^16 7.10641 
2^18 9.05811 
2^20 10.3053 
2^22 11.6851 
2^24 12.6975 
2^26 14.6125 
2^28 16.0617 

Während Größe exponentiell wächst, die Zahl der Elemente greift fast linear wächst, so erwartete Zeitkomplexität für zufällige Permutationen ist so etwas wie O (n log n).

Answer 2

Das Invertieren eines Arrays A erfordert, dass wir eine Permutation B finden, die die Anforderung A[B[i]] == i für alle i erfüllt.

Um die Inverse in-place zu erstellen, müssen wir Elemente und Indizes vertauschen, indem wir A[A[i]] = i für jedes Element A[i] festlegen. Offensichtlich würden wir, wenn wir einfach durch A iterieren und die oben erwähnte Ersetzung durchführen, die bevorstehenden Elemente in A überschreiben, und unsere Berechnung würde fehlschlagen.

Daher müssen wir Elemente und Indizes entlang Zyklen von A tauschen, indem wir c = A[c] folgen, bis wir den Startindex unseres Zyklus c = i erreichen.

Jedes Element von A gehört zu einem solchen Zyklus. Da wir keinen Platz zum Speichern haben, ob ein Element A[i] bereits verarbeitet wurde und übersprungen werden muss, müssen wir seinem Zyklus folgen: Wenn wir einen Index c < i erreichen, wissen wir, dass dieses Element Teil eines zuvor verarbeiteten Zyklus ist.

Dieser Algorithmus hat eine Worst-Case-Laufzeit-Komplexität von O (n²) eine durchschnittliche Laufzeitkomplexität von O (n log n) und eine Best-Case-Laufzeitkomplexität von O (n).

function invert(array) { 
 
    main: 
 
    for (var i = 0, length = array.length; i < length; ++i) { 
 
    
 
    // check if this cycle has already been traversed before: 
 
    for (var c = array[i]; c != i; c = array[c]) { 
 
     if (c <= i) continue main; 
 
    } 
 
    
 
    // Replacing each cycle element with its predecessors index: 
 
    var c_index = i, 
 
     c = array[i]; 
 
    do { 
 
     var tmp = array[c]; 
 
     array[c] = c_index; // replace 
 
     c_index = c; // move forward 
 
     c = tmp; 
 
    } while (i != c_index) 
 
     
 
    } 
 
    return array; 
 
} 
 
    
 
console.log(invert([3, 1, 0, 2, 4])); // [2, 1, 3, 0, 4]

Beispiel fürA = [1, 2, 3, 0]:

1. das erste Element bei Index gehört zum Zyklus der Elemente 1 - 2 - 3-0. Sobald wir die Indizes 0, 1, 2 und 3 entlang dieses Zyklus verschoben haben, haben wir den ersten Schritt abgeschlossen.

2. Das nächste Element bei Index gehört zur gleichen Zyklus und unsere Check sagt uns so in nur einem Schritt (da es ein Rückschritt ist).

3. Das gleiche gilt für die übrigen Elemente und .

   

Insgesamt führen wir 4 + 1 + 1 + 1 'Betrieb'. Dies ist das Best-Case-Szenario.