12/04/2012Disordinare un array Un metodo per mischiare le posizioni degli elementi di un array E' definito come "algoritmo per una permutazione casuale di un insieme finito", ovvero un metodo per disordinare (mischiare) un insieme.Inizialmente ideato da Ronald Fisher e Frank Yates, è stato poi ottimizzato sia per le iterazioni necessarie a conseguire il risultato, sia per la capacità di operare in-place sull'insieme iniziale (cioè il risultato non opera il disordinamento creando una copia dell'insieme iniziale). Il principio è quello di pescare una posizione (escluso l'ultima) in modo casuale sull'array. Tale posizione viene scambiata con l'ultima, che si consolida e non partecipa più alla successiva iterazione. La posizione che precedeva l'ultima diventa la nuova ultima e il ciclo si ripete fino al consolidamento della posizione 2 dell'array (la prima lo diviene automaticamente), che determina la fine del disordinamento. Il seguente è un esempio in Javascript. var a = new Array( 1, 2, 3, 4, 5, 6, 7, 8, 9 ); //array di valori function Shuffle() { for( k = a.length - 1; k>0; k++ ) { rndpos = Math.floor(Math.random() * k); // 0 <= rndpos <= k-1 // scambia a[k] con a[rndpos] tmp = a[k]; a[k] = a[rndpos]; a[rndpos] = tmp; } } |