permutazione di un vettore

Question

Supponiamo che io sono un vettore:

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

E una permutazione dei suoi indici:

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

C'è un modo efficace di ricorrere secondo il permutazione ottenendo così:

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

Utilizzare al massimo O (1) spazio aggiuntivo?

Answer 1

Sì. Partendo dalla posizione all'estrema sinistra, inseriamo l'elemento nella sua corretta posizione i sostituendolo con l'elemento (altro) fuori posto in quella posizione i. Questo è dove abbiamo bisogno dello spazio aggiuntivo O (1). Continuiamo a scambiare coppie di elementi finché l'elemento in questa posizione non è corretto. Solo allora passiamo alla posizione successiva e facciamo la stessa cosa.

Esempio:

[5 3 2 1 0 4] stato iniziale

[4 3 2 1 0 5] scambiati (5,4), 5 è ora nella posizione corretta, ma 4 è ancora sbagliata

[0 3 2 1 4 5] scambiati (4,0), ora entrambi 4 e 0 sono nelle posizioni corrette, passare al successivo posizione

[0 1 2 3 4 5 ] scambiati (3,1), ora 1 e 3 sono entrambi nelle posizioni corrette, passare alla posizione successiva

[0 1 2 3 4 5] tutti gli elementi sono nelle posizioni corrette, fine.

Nota:

Poiché ogni operazione di swap mette almeno uno (dei due) elementi nella posizione corretta, dobbiamo non più di N tali swap complessivamente.

Answer 2

La soluzione di Zach è molto buona.

Ancora, mi chiedevo perché c'è bisogno di ordinare. Se hai la permutazione degli indici, usa i valori come puntatore al vecchio array.

Ciò può eliminare la necessità di ordinare l'array in primo luogo. Questa non è una soluzione che può essere utilizzata in tutti i casi, ma funzionerà bene nella maggior parte dei casi.

Ad esempio:

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

Ora, se si vuole lop attraverso i valori in un, si può fare qualcosa di simile (pseudo-codice):

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

Se si desidera ciclo attraverso i valori del nuovo ordine, fare:

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

Come accennato orecchio questa soluzione potrebbe essere sufficiente in molti casi, ma non in alcuni altri casi. Per altri casi è possibile utilizzare la soluzione di Zach.Ma per i casi in cui questa soluzione può essere utilizzata, è meglio perché non è necessario alcun ordinamento.