Permutazione di un vettore
-
22-08-2019 - |
Domanda
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?
Soluzione
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.
Altri suggerimenti
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.