Rimescolare un array

Scrivete una funzione shuffle(array) che rimescoli (riordini casualmente) gli elementi di un array.

Esecuzioni multiple di shuffle dovrebbero portare a diversi ordinamenti degli elementi. Ad esempio:

          let arr = [1, 2, 3];

shuffle(arr);
// arr = [3, 2, 1]

shuffle(arr);
// arr = [2, 1, 3]

shuffle(arr);
// arr = [3, 1, 2]
// ...
        

Tutti gli elementi ordinati dovrebbero avere una probabilità identica. Ad esempio, [1,2,3] può essere riordinato come [1,2,3] o [1,3,2] o [3,1,2] etc; ognuno dei casi deve avere la stessa probabilità.

La soluzione più semplice potrebbe essere:

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

let arr = [1, 2, 3];
shuffle(arr);
alert(arr);

Questa in qualche modo funziona, perché Math.random() - 0.5 è un numero casuale che può essere sia positivo che negativo, quindi la funzione riordina gli elementi casualmente.

Con questa funzione di ordinamento, non tutte le permutazioni hanno la stessa probabilità.

Ad esempio, considerando il codice sotto. Esegue shuffle 1000000 di volte e conta il numero di occorrenze di tutti i risultati possibili:

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

// counts of appearances for all possible permutations
let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join('')]++;
}

// show counts of all possible permutations
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

Un esempio di risultato possibile (dipende dal motore JS):

          123: 250706
124425
249618
124880
125148
125223
        

Possiamo chiaramente vedere che le combinazioni 123 e 213 appaiono molto più spesso delle altre.

Il risultato del codice potrebbe variare in base al motore JavaScript, ma già possiamo notare che questo tipo di approccio è inaccettabile.

Perché non funziona? Generalmente parlando, sort è una “scatola nera”: gli passiamo un array ed una funzione di confronto e ci aspettiamo di ottenere l’array ordinato. Ma a causa della difficoltà nell’implementazione della casualità la scatola nera potrebbe funzionare male; quanto male, dipende dal motore JavaScript.

Esistono altri modi per questo compito. Ad esempio, c’è un ottimo algoritmo chiamato Fisher-Yates shuffle. L’idea è di attraversare l’array in ordine inverso e di scambiare l’elemento con un altro casuale, che venga prima di lui:

          function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1)); // indice casuale da 0 a i

    //scambia gli elementi array[i] e array[j]
    // usiamo la sintassi "destructuring assignment"
    //troverai maggiori dettagli su questa sintassi nei capitoli seguenti
    //potrebbe essere scritto come
    // let t = array[i]; array[i] = array[j]; array[j] = t
    [array[i], array[j]] = [array[j], array[i]];
  }
}
        

Proviamo ad eseguire lo stesso test:

function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
}

// counts of appearances for all possible permutations
let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join('')]++;
}

// show counts of all possible permutations
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

Un possibile risultato:

          123: 166693
166647
166628
167517
166199
166316
        

Ora sembra funzionare: tutte lo occorrenze appaiono con la stessa probabilità.

Inoltre, anche le performance dell’algoritmo Fisher-Yates sono migliori, poichè non è richiesto alcun riordinamento.