Algoritmo Fisher-Yates

El algoritmo de desordenamiento Fisher-Yates es un algoritmo para generar una permutación aleatoria de un conjunto finito. O en otras palabras, es un algoritmo para barajar una lista. Es uno de los algoritmos clásicos descrito en 1938 por Ronald Fisher y Frank Yates, que fue mejorado en 1964 por Richard Durstenfeld, y popularizado por Donald E. Knuth en The Art of Computer Programming. A lo largo del tiempo se han propuesto varias implementaciones del algoritmo, pero la más popular y moderna es la de Durstenfeld, que es la que vamos a ver en este artículo.

Utilizaré JavaScript para mostrar los pasos, pero es fácilmente replicable en cualquier lenguaje de programación.

El algoritmo

Partimos de una secuencia de elementos y una lista vacía.

listaOriginal = ["A", "B", "C", "D", "E", "F", "G", "H"];
listaMezclada = [];

Seleccionamos una posición aleatoria de la lista original entre 0 y el tamaño de la lista menos 1 (7).

En el ejemplo la posición seleccionada es 2, por lo tanto la letra “C” se añade a la lista mezclada y se elimina de la lista original.

listaOriginal = ["A", "B", "D", "E", "F", "G", "H"];
listaMezclada = ["C"];

Repetimos el proceso. Seleccionamos una posición aleatoria de la lista original entre 0 y el tamaño de la lista menos 1 (6).

La posición aleatoria es 4. La letra “F” se añade al inicio lista mezclada y se elimina de la lista original.

listaOriginal = ["A", "B", "D", "E", "G", "H"];
listaMezclada = ["F", "C"];

Y repetimos el proceso hasta que la lista original esté vacía.

listaOriginal = [];
listaMezclada = ["H", "G", "A", "B", "E", "D", "F", "C"];

Ya tenemos la lista mezclada.

Implementación

Voy a dar 2 formar de implementar en JavaScript.

La primera será la tradicional, usando un bucle while y splice para eliminar el elemento de la lista original.

function mezclar(lista) {
  let listaMezclada = [];
  // Copiamos la lista original para no modificarla
  let listaOriginal = lista.slice();

  while (listaOriginal.length > 0) {
    let posicion = Math.floor(Math.random() * listaOriginal.length);
    let elemento = listaOriginal.splice(posicion, 1)[0];
    listaMezclada.unshift(elemento);
  }

  return listaMezclada;
}

mezclar(["A", "B", "C", "D", "E", "F", "G", "H"]);
// [ "C", "G", "E", "A", "B", "F", "H", "D" ]

Si calculamos su eficiencia podemos ver buenos resultados. En el peor de los casos, cuando la lista está ordenada, el algoritmo tiene una eficiencia de O(n²). Pero en el mejor de los casos, cuando la lista está desordenada, la eficiencia es de O(n).

Vamos a probar el rendimiento con una secuencia incremental con 10000 elementos ([0, 1, 2, 3... 10000]).

// Creamos la lista
const lista10000 = Array.from({length: 10000}, (v, i) => i);

function mezclar(lista) {
  let listaMezclada = [];
  // Copiamos la lista original para no modificarla
  let listaOriginal = lista.slice();

  while (listaOriginal.length > 0) {
    let posicion = Math.floor(Math.random() * listaOriginal.length);
    let elemento = listaOriginal.splice(posicion, 1)[0];
    listaMezclada.unshift(elemento);
  }

  return listaMezclada;
}

// Medimos el tiempo de ejecución al inicio
const start = performance.now();
// Ejecutamos la función
mezclar(lista10000);
// Medimos el tiempo de ejecución al final
const end = performance.now();
// Mostramos el tiempo de ejecución
console.log(`${end - start} ms`);

En mi equipo, ha dando unos resultados de 21 ms.

Ahora vamos a implementar de de otra forma. En esta ocasión usaremos algunas características de la programación funcional, en este caso la inmutabilidad y la recursividad, con el objetivo de gestionar mejor la memoria y aumentar el desempeño.

function mezclar(listaOriginal, listaMezclada=[]) {
    // Si no hay elementos en la lista original devolvemos la lista mezclada y terminamos la recursividad
    if (listaOriginal.length === 0) {
        return listaMezclada;
    }
    // Seleccionamos una posición aleatoria de la lista original entre 0 y el tamaño de la lista menos 1
    const posicionAleatoria = Math.floor(Math.random() * listaOriginal.length);
    // Creamos una nueva lista original sin el elemento seleccionado
    const nuevaListaOriginal = listaOriginal.filter((_, index) => index !== posicionAleatoria);
    // Creamos una nueva lista mezclada con el elemento seleccionado al inicio
    const nuevaListaMezclada = listaMezclada.concat(listaOriginal[posicionAleatoria]);
    // Llamamos a la función recursivamente
    return mezclar(nuevaListaOriginal, nuevaListaMezclada);
}

Ahora tarda 16ms, hemos recortado 5ms. ¡No esta nada mal!

Bonus, implementación en Elisp

Voy a implementar el algoritmo en Elisp, el lenguaje de programación de Emacs.

(defun mezclar (listaOriginal &optional listaMezclada)
  "Aplica el algoritmo de mezcla de Fisher-Yates a una lista."
  (if (null listaOriginal)
      ;; Terminamos la recursividad, devolvemos la lista mezclada
      listaMezclada
      ;; En caso contrario continuamos con la lógica
    (let* ((posicionAleatoria (random (length listaOriginal)))
       (elementoAleatorio (nth posicionAleatoria listaOriginal))
       ;; Creamos una nueva lista original sin posicionAleatoria
       (listaOriginalSinElementoAleatorio (append (cl-subseq listaOriginal 0 posicionAleatoria) (nthcdr (1+ posicionAleatoria) listaOriginal)))
       ;; Creamos una nueva lista mezclada con el elemento seleccionado al inicio
       (nuevaListaMezclada (if (null listaMezclada) (list elementoAleatorio) (cons elementoAleatorio listaMezclada))))
      ;; Llamamos recursivamente a la función mezclar con la nueva lista original y la nueva lista mezclada
      (mezclar listaOriginalSinElementoAleatorio nuevaListaMezclada))))

(mezclar '(1 2 3 4 5))
;; (3 1 5 2 4)

Si quieres medir el rendimiento puedes hacer lo siguiente.

(let ((max-lisp-eval-depth 10000000)
      (secuencia (number-sequence 0 10000))
      (start nil)
      (end nil))
  (setq start (current-time))
  (mezclar secuencia)
  (setq end (current-time))
  (message "%f"  (float-time (time-subtract end start))))

En mi equipo obtengo 10s. Una diferencia muy grande con Node (que es el interprete que he usado en las pruebas). Tal vez no sea una comparación justa, pero es lo que hay. Y para aquellos que me pidan compilarlo a .elc, no he notado ninguna mejora.

Espero que os sirva de inspiración.

Bonus, implementación en Python

Y por último, una implementación en Python.

import random

def mezclar(lista_original, lista_mezclada=[]):
    """
    Función recursiva para mezclar una lista de forma aleatoria.

    Args:
        lista_original (list): La lista original que queremos mezclar.
        lista_mezclada (list, opcional): La lista que contiene los elementos mezclados.
            Por defecto, es una lista vacía.

    Returns:
        list: La lista original mezclada de forma aleatoria.
    """
    if len(lista_original) == 0:
        return lista_mezclada

    posicion_aleatoria = random.randint(0, len(lista_original) - 1)
    elemento_seleccionado = lista_original.pop(posicion_aleatoria)

    nueva_lista_mezclada = lista_mezclada + [elemento_seleccionado]

    return mezclar(lista_original, nueva_lista_mezclada)

# Ejemplo de uso:
lista_original = [1, 2, 3, 4, 5]
lista_mezclada = mezclar(lista_original)
print(lista_mezclada)

Conclusiones

El algoritmo de mezcla Fisher-Yates es un algoritmo muy eficiente para barajar una lista. Es fácil de implementar y tiene una eficiencia fantástica. Por supuesto que existen otros algoritmos, pero este es uno de los más sencillos, populares y eficientes.

Algoritmo JavaScript Python elisp