Algoritmo per generare ordine casuale di elementi

Question

Come ordinare in modo casuale circa 20 elementi con la complessità più bassa? (generazione di permutazioni casuali)

Answer 1

Knuth's shuffle algorithm è una buona scelta.

Answer 2

Alcuni mesi fa ho eseguito il blogging per ottenere una permutazione casuale di un elenco di numeri interi. Potresti usarlo come una permutazione degli indici del set che contiene i tuoi elementi, e poi hai quello che vuoi.

• Generating random int list in F#

• Uniformly distributed random list permutation in F#

Nel primo post mi esplorare alcune possibilità, ed infine ottengo "una funzione per permutate caso un elenco generico con O (n) complessità" , correttamente incapsulato per lavorare su dati immutabili (cioè, è privo di effetti collaterali).

Nel secondo post, lo distribuisco in modo uniforme.

Il codice è in F #, spero che non ti dispiaccia!

Buona fortuna.

EDIT: Non ho una prova formale, ma l'intuizione mi dice che la complessità di un tale algoritmo non può essere inferiore a O (n). Mi piacerebbe davvero vederlo fatto più velocemente!

Answer 3

Un modo semplice per rendere casuale l'ordine è creare un nuovo elenco delle dimensioni corrette (20 nel tuo caso), scorrere il primo elenco e aggiungere ciascun elemento in una posizione casuale al secondo elenco. Se la posizione casuale è già occupata, mettila nella successiva posizione libera.

penso che questo pseudocodice è corretto:

list newList 
foreach (element in firstList) 
    int position = Random.Int(0, firstList.Length - 1) 
    while (newList[position] != null) 
     position = (position + 1) % firstList.Length 
    newList[position] = element 

EDIT: Così si scopre che questa risposta non è in realtà che una buona. Non è né particolarmente veloce, né particolarmente casuale. Grazie per i vostri commenti. Per una buona risposta, si prega di scorrere indietro all'inizio della pagina :-)

Answer 4

Probabilmente qualcuno ha già implementato il mischiare per voi. Ad esempio, in Python è possibile utilizzare random.shuffle, in C++ random_shuffle e in PHP shuffle.