Permutazione di un vettore

Question

supponiamo di avere 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]

Esiste un modo efficiente per ricorrerlo in base alla permutazione ottenendo così:

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

Utilizzando al massimo O(1) spazio aggiuntivo?

Answer 1

SÌ.Partendo dalla posizione più a sinistra, mettiamo il elemento lì nella sua versione corretta posizione i scambiandolo con l'(altro) elemento fuori posto in quella posizione i.Qui è dove abbiamo bisogno dello spazio aggiuntivo O(1).Continuiamo a scambiare coppie di elementi finché l'elemento in questa posizione non è corretto.Solo allora procediamo alla posizione successiva e facciamo la stessa cosa.

Esempio:

[5 3 2 1 0 4] stato iniziale

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

[0 3 2 1 4 5] scambiato (4,0), ora sia 4 che 0 sono nella posizione corretta, passa alla posizione successiva

[0 1 2 3 4 5] scambiato (3,1), ora 1 e 3 sono entrambi nella posizione corretta, passa alla posizione successiva

[0 1 2 3 4 5] tutti gli elementi sono nella posizione corretta, fine.

Nota:

Poiché ogni operazione di scambio mette almeno uno (dei due) elementi nella posizione corretta, non abbiamo bisogno di più di N scambi di questo tipo in totale.

Answer 2

La soluzione di Zach è molto buona.

Ancora, mi chiedevo perché non v'è alcuna necessità di ordinare. Se avete la permutazione degli indici, utilizzare i valori come puntatore alla vecchia serie.

Questo può eliminare la necessità di ordinare l'array in primo luogo. Questa non è una soluzione che può essere utilizzato 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 di a , si può fare qualcosa di simile (pseudo-codice):

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

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

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

Come accennato in precedenza, questo soluion può essere sufficiente in molti casi, ma non può in alcuni altri casi. Per gli altri casi è possibile utilizzare la soluzione Zach.But per i casi in cui questa soluzione può essere utilizzata, è meglio perché nessun ordinamento è necessaria a tutti.