Barajar un array

Escribe la función shuffle(array) que baraje (reordene de forma aleatoria) los elementos del array.

Múltiples ejecuciones de shuffle puede conducir a diferentes órdenes de elementos. Por ejemplo:

          let arr = [1, 2, 3];

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

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

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

Todos los reordenamientos de elementos tienen que tener la misma probabilidad. Por ejemplo, [1,2,3] puede ser reordenado como [1,2,3] o [1,3,2] o [3,1,2] etc, con igual probabilidad en cada caso.

Una solución simple podría ser:

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

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

Eso funciona de alguna manera, porque Math.random() - 0.5 es un número aleatorio que puede ser positivo o negativo, por lo tanto, la función de ordenamiento reordena los elementos de forma aleatoria.

Pero debido a que la función de ordenamiento no está hecha para ser usada de esta manera, no todas las permutaciones tienen la misma probabilidad.

Por ejemplo, consideremos el código siguiente. Ejecuta shuffle 1000000 veces y cuenta las apariciones de todos los resultados posibles:

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

// cuenta las apariciones para todas las permutaciones posibles
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('')]++;
}

// muestra conteo de todas las permutaciones posibles
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

Un resultado de ejemplo (depende del motor JS):

          123: 250706
124425
249618
124880
125148
125223
        

Podemos ver una clara tendencia: 123