La solución óptima para barajar una matriz en Javascript

Muy buenas, soy Miguel y en esta ocasión les traigo un nuevo artículo.

Recientemente me encontré con un pequeño problema al crear una nueva matriz ordenada aleatoriamente basada en una anterior. Para hablar brevemente, el objetivo final es obtener una matriz barajada.

La siguiente es mi solución después de unos momentos de experimento antes de buscar en la web. (Pensé que podía hacerlo yo mismo con un pequeño código : p)

var arr = [1, 2, 3, 4, 5, 6, 7]
function shuffle (arr) {
let i = 0,
res = [],
index  while (i <= arr.length - 1) {
index = Math.floor(Math.random() * arr.length)    
if (!res.includes(arr[index])) {
res.push(arr[index])
i++
}
}
  return res
}
// expected
arr = shuffle(arr)
// [6, 3, 4, 1, 7, 2, 5]

Como puede ver, esta no es una buena forma de manejar la mezcla, así que decido investigar un poco al respecto.

Después de buscar algunas respuestas en google y stackoverflow, encontré una muy satisfactoria solución para mezclar una matriz. (La respuesta ha estado ahí desde 2010 ... pero, de hecho, muy calificada).

Lo primero es lo primero, echemos un vistazo a la respuesta. Es bastante simple pero lo suficientemente rápido.

function shuffle(array) {
var currentIndex = array.length, temporaryValue, randomIndex;
// While there remain elements to shuffle...
while (0 !== currentIndex) {
// Pick a remaining element...
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// And swap it with the current element.
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}

Por qué mi solución es mala

Al principio, estaba pensando en crear nuevos índices aleatorios dentro de un bucle while y empuje el elemento de matriz anterior a una nueva matriz como retorno.

while (i <= arr.length - 1) { 
// crear índice de 
índice aleatorio = Math.floor (Math.random () * arr.length)
// inserta el elemento en la nueva matriz 
if (! res.includes (arr [index])) { 
res.push (arr [index]) 
i ++ 
} 
}

Funciona bien con devoluciones muy satisfactorias. Pero la complejidad del tiempo fue bastante mala. En el bucle while, comprueba si el elemento a insertar existe en la nueva matriz para cada una de las vueltas del bucle. Esto resulta en O (n2).

Si una matriz no es tan grande, entonces mi función estaba bien. Pero la verdad es que mi proyecto necesita generar una lista con más de 1000 elementos.

Entonces es mejor optimizar el algoritmo. (Creo que siempre es mejor hacer esa optimización. No tenga miedo de referirse a las computadoras: D)

La baraja Fisher-Yates

La respuesta de stackoverflow parece bastante simple, sin embargo, de hecho, utiliza un algoritmo inventado por Ronald Fisher y Frank Yates.

El shuffle de Fisher-Yates es un algoritmo para generar una permutación aleatoria de una secuencia finita; en términos sencillos, el algoritmo baraja la secuencia.

… y también se conoce como la reproducción aleatoria de Knuth después de Donald Knuth.

– Desde Wikipedia.

Hay un artículo de blog antiguo que visualiza el algoritmo de reproducción aleatoria. https://bost.ocks.org/mike/shuffle/

la función shuffle es una descripción del algoritmo.

function shuffle(array) {
var currentIndex = array.length, temporaryValue, randomIndex;
// While there remain elements to shuffle...
while (0 !== currentIndex) {
// Create a random index to pick from the original array
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// Cache the value, and swap it with the current element
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}

La solución es muy buena, pero todavía tiene algunas posibilidades de mejora. Creo que hacer una función pura aquí tiene más sentido. Así que prefiero devolver una nueva matriz que modificar el argumento original como efecto secundario.

Para evitar modificar los datos originales, también puedo crear un clon mientras paso el arugment.

shuffle(arr.slice(0))

Otras variaciones

Hay algunas alternativas honorables a la solución que encontré en stackoverflow que creo que está correctamente optimizado.

La baraja de Durstenfeld

Esta solución aparece en la página de stackoverflow. Encontré un memorando esencial al final.

// Pre-ES6
function shuffleArray(array) {
for (var i = array.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// ES6+
function shuffleArray(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]];
}
}

Método de extensión de matriz

En realidad, preferiría este por su simplicidad y un pequeño truco de números redondos. El truco aquí es usar >>> (operador de cambio a la derecha sin firmar) en lugar de Math.floor.

Array.prototype.shuffle = function() {
let m = this.length, i;
while (m) {
i = (Math.random() * m--) >>> 0;
[this[m], this[i]] = [this[i], this[m]]
}
return this;
}

Bien, eso es todo para la investigación. Espero que también comprenda bien el algoritmo shuffle de este artículo. Si crees que este artículo es genial, compártelo en las redes sociales.

Espero que te sea de utilidad. Gracias por leer este artículo.