Cómo reordenar un array de forma (realmente) aleatoria

Javascript es uno de los lenguajes más utilizados del mundo y ocupa los primeros lugares hace rato. Codear en JS es muy cómodo, posee innumerables librerías y métodos que te hacen la vida más sencilla y, a la hora de resolver problemas, es común utilizarlos.

Recientemente, en un proyecto, tuve que armar una pequena función para reordenar aleatoriamente un array n cantidad de veces. Fui a lo más simple, que era utilizar sort() junto Math.random(), el resultado fue el esperado:

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

let arr = [1, 2, 3];

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

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

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

Sort() es un método para ordenar un array, al que le podemos dar como parámetro una función que defina la forma de ordenamiento. Si se omite, el array es ordenado según la posición del valor Unicode de cada caracter, según la conversión a string de cada elemento.

Math.random() retorna un punto flotante, un número pseudo-aleatorio dentro del rango [0, 1). Desde el 0 (que está incluido) hasta el 1 pero sin incluirlo. De este modo, en este caso, la resta modifica el valor de aleatoriedad y da como resultado un número que puede ser positivo o negativo. Por lo que la función shuffle() reordena los elementos al «azar».

Hasta ahí perfecto, pero mi idea era que todos los posibles reordenamientos del array tengan la misma probabilidad, es decir que sea lo más random posible. A simple vista no se nota, pero si evaluamos más exhaustivamente el reordenamiento podemos ver que hay cierta patrones que se repiten.

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

// creo un objeto de todos los posibles ordenamientos
let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

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

// imprimo el recuento de todos los reordenamientos
for (let key in count) {
  console.log(`${key}: ${count[key]}`);
}

Un resultado (que depende del motor de JS):

Hay un patrón marcado de 123, 213 y 321 en este caso. Mirá el código en CodeSandbox.

¿Cómo reordenar el array sin patrones que se repitan más que otros? Es decir, de forma realmente aleatoria.

Hay un algoritmo llamado Fisher-Yates shuffle para generar un permutación aleatoria de una secuencia finita. Para decirlo de una forma sencilla: el algoritmo produce un reordenamiento donde cada permutación es igualmente probable. Recorremos la matriz en orden inverso e intercambiaremos cada elemento con uno aleatorio antes:

function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1)); // índice random entre 0 e i

    // intercambiamos los valores de array[i] y array[j]
    // usamos "destructuring assignment"
    [array[i], array[j]] = [array[j], array[i]];
  }
}

El resultado es el esperado:

Puedes chequear el código aquí.

¡Gracias por leer!