Permutation eines Vektors

Question

annehmen, habe ich einen Vektor:

0 1 2 3 4 5 
[45,89,22,31,23,76] 

Und eine Permutation ihrer Indizes:

[5,3,2,1,0,4] 

Gibt es eine effiziente Möglichkeit, es zu greifen, nach der Permutation so zu erhalten:

[76,31,22,89,45,23] 

Verwenden Sie höchstens O (1) zusätzlichen Speicherplatz?

Answer 1

Ja. Ausgehend von der äußersten linken Position setzen wir das Element dort in seine korrekte Position, indem wir es mit dem (anderen) falsch platzierten Element an dieser Position austauschen. Hier benötigen wir den O (1) zusätzlichen Platz. Wir tauschen Paare von Elementen solange um, bis das Element in dieser Position korrekt ist. Nur dann gehen wir zur nächsten Position und machen dasselbe.

Beispiel:

[5 3 2 1 0 4] Anfangszustand

[4 3 2 1 0 5] ausgetauscht (5,4), 5 nun in der richtigen Position ist, aber 4 ist immer noch falsch

[0 1 3 2 4 5] ausgetauscht (4,0), sowohl jetzt 4 und 0 in den richtigen Positionen sind, auf zur nächsten Position bewegen

[0 1 2 3 4 5 ] getauscht (3,1), jetzt sind 1 und 3 beide in der richtigen Position, gehe zur nächsten Position

[0 1 2 3 4 5] alle Elemente sind in den richtigen Positionen, Ende.

Hinweis:

Da jede Swap-Operation mindestens einer (der beiden) Elemente in der richtigen Position bringt, brauchen wir nicht mehr als N solche Swaps zusammen.

Answer 2

Zachs Lösung ist sehr gut.

Trotzdem habe ich mich gefragt, warum es nötig ist zu sortieren. Wenn Sie die Permutation der Indizes verwenden, verwenden Sie die Werte als Zeiger auf das alte Array.

Dies kann die Notwendigkeit beseitigen, das Array an erster Stelle zu sortieren. Dies ist keine Lösung, die in allen Fällen verwendet werden kann, aber es wird in den meisten Fällen gut funktionieren.

Zum Beispiel:

a = [45,89,22,31,23,76]; 
b = [5,3,2,1,0,4] 

Nun, wenn Sie in ein durch die Werte stutzen wollen, können Sie so etwas wie (Pseudo-Code) tun:

for i=0 to 4 
{ 
    process(a[i]); 
} 

Wenn Sie möchten, Schleife durch die Werte in der neuen Reihenfolge, tun:

for i=0 to 4 
{ 
    process(a[b[i]]); 
} 

Wie erwähnt Ohr Diese Lösung kann in vielen Fällen ausreichend sein, in einigen anderen Fällen jedoch nicht. Für andere Fälle können Sie die Lösung von Zach verwenden.Aber für die Fälle, in denen diese Lösung verwendet werden kann, ist es besser, da überhaupt keine Sortierung erforderlich ist.