Permutation eines Vektors

Question

Angenommen, ich habe 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 nach der Permutation greift somit zu erhalten:

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

Mit höchstens O (1) zusätzlichem Raum?

Answer 1

Ja. Ausgehend von der Position ganz links, wir setzen das -Element es in seiner korrekten Position i indem sie sie mit der (anderen) verlegt Element an dieser Position tauschen i. Dies ist, wo wir die O (1) zusätzlichen Platz benötigen. Wir halten Paare von Elementen herum, bis das Element in dieser Position tauschen korrekt ist. Erst dann gehen wir in die nächste Position und das gleiche tun.

Beispiel:

[5 3 2 1 0 4] Anfangszustand

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

[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] ausgetauscht (3,1), jetzt 1 und 3 sind sowohl in den richtigen Positionen, an bis zur nächsten Position bewegen

[0 1 2 3 4 5] sind alle Elemente in der richtigen Position, end.

Hinweis :

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

Answer 2

Zachs Lösung ist sehr gut.

Aber ich habe mich gefragt, warum es eine Notwendigkeit zu sortieren ist. Wenn Sie die Permutation der Indizes haben, verwenden Sie die Werte als Zeiger auf das alte Array.

Dies kann die Notwendigkeit beseitigen, die Anordnung in erster Linie 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 durch die Werte stutzen wollen in a , können Sie so etwas wie (Pseudo-Code) tun:

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

Wenn Sie eine Schleife durch die Werte in der neuen Ordnung wollen, tun:

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

Wie bereits erwähnt, diese soluion kann in vielen Fällen ausreichend sein, kann aber nicht in einigen anderen Fällen. In anderen Fällen können Sie die Lösung von Zach.But für die Fälle verwenden, in denen diese Lösung verwendet werden kann, ist es besser, weil keine Sortierung überhaupt benötigt wird.