Un modo efficiente di randomizzazione un array - codice casuale

Question

mi è stato chiesto a questa domanda in un'intervista e ho dato diverse soluzioni, ma l'intervistatore non era convinto. Sono interessato a trovare una soluzione. Si prega di gettare in vostro punto di vista:

D: Scrivere una struttura dati efficiente per attuare il riordino in un ipod. Si deve giocare tutte le canzoni, ogni volta in ordine casuale diverso, la stessa canzone non deve essere ripetuto. (Per lo più O (n))

Una soluzione, ho pensato che dopo l'intervista: che posso fare uno studio randomizzato rapido sorta, senza ricorsione. Dove a caso, scelto 1 perno O (1) e poi fare quicksort O (n). Ora canzoni saranno ordinati in un certo ordine e li giocare fino alla fine. Una volta raggiunta la fine, io Ancora scelto un perno casuale e ripetere più volte questo processo.

Saluti, Sethu

Answer 1

Inserisci tutte le canzoni in un array ... Per ogni elemento dell'array scambio con una posizione casuale.

Answer 2

Si desidera che il Fisher-Yates Shuffle . Essere consapevoli degli errori di implementazione menzionati su quella pagina, come la risposta attualmente accettato cade fallo di uno.

Answer 3

Bene, la prima soluzione in tempo lineare che viene in mente:

Si potrebbe fare una lista concatenata di tutte le canzoni, che vorrebbero circa O (n) (dato che gli inserimenti sono operazioni costante di tempo). Poi, genera un numero casuale, modulo il formato della lista per avere un indice casuale, e rimuovere tale indice e aggiungerlo a una nuova lista (entrambi i quali sono operazioni di tempo costanti).

Un inserimento per ciascun O (n) + una rimozione per ciascuna O (n) + un secondo O inserimento (n). Questo complesso portare ad una soluzione di tempo lineare.

Modifica : ho completamente dimenticato di camminare lista. Così, invece, si potrebbe rendere il risultato un array di lunghezza fissa. Pop il capo della lista collegata, assegnare l'indice casuale e compilare la matrice.

Answer 4

Nate (a cura) e Brian di algoritmi sono il Fisher-Yates riordino O (n), mentre si mescola di classificare è O (nlogn), ma possono in realtà essere più veloce in pratica (http://en.wikipedia.org/wiki / Fisher% E2% 80% 93Yates_shuffle # Comparison_with_other_shuffling_algorithms). Ottenere canzone rimescolamento sbagliata può avere conseguenze insignificanti, ma se si sta scrivendo un algoritmo di rimescolamento per un gioco di poker on-line, assicurarsi di sapere cosa si sta facendo (http://www.cigital.com/news/index.php?pg= arte & artid = 20).

Answer 5

Sono un principiante, lasciatemi dire una soluzione che gli scioperi a mente, se qualcosa è sbagliato favore, mi fanno sapere.

lascia supporre canzoni sono memorizzati nella lista sia collegata singolarmente o doppiamente. Ogni volta che il lettore musicale si apre scegliere un numero casuale minore di (qualsiasi numero che si desidera) assumere k, e invertire ogni k nodi nella lista, in modo simile farlo due volte o tre volte max (a piacere), che avrebbe preso O ( 2n) o o (3n tempo) per la riproduzione casuale. finalmente avere un puntatore all'ultimo nodo della lista. E ogni volta che un brano viene ascoltato (un nodo viene visitato) rimuovere il nodo e inserirla accanto l'ultimo nodo che può essere fatto in O (1) tempo. Questo continua fino a quando il lettore musicale è chiuso.

Grazie, Desideroso di conoscere la correttezza della risposta.

Answer 6

Quello che vogliamo è il Fisher-Yates Shuffle . Ecco un'implementazione in Java:

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

Come funziona è tratta l'intero array come un cappello e inizia a trascinare elementi casuali e li fila alla parte anteriore della matrice. Tutti gli elementi dopo i sono 'nel secchio', tutti gli elementi prima i vengono mescolate.