Cómo mezclar líneas (y por qué importa Fisher-Yates)

Qué hace Fisher-Yates

El algoritmo es corto. Recorre la lista del final al principio. En cada posición i, elige un índice aleatorio j en el rango de 0 a i. Intercambia los elementos en i y j. Pasa a la posición anterior. Detente en el índice 1.

Eso es todo. Tras el recorrido, la lista queda permutada de forma uniformemente aleatoria. Cada una de las n! ordenaciones posibles es igual de probable.

Implementación en JavaScript:

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

Python:

import random
def shuffle(arr):
    for i in range(len(arr) - 1, 0, -1):
        j = random.randint(0, i)
        arr[i], arr[j] = arr[j], arr[i]
    return arr

Seis líneas. Tiempo lineal. Distribución uniforme. Las funciones de la biblioteca estándar en la mayoría de los lenguajes (random.shuffle en Python, shuffle en Ruby) implementan Fisher-Yates por dentro.

La mezcla rota — ordenar por una clave aleatoria

Una mezcla intuitiva pero rota:

// NO HAGAS ESTO
arr.sort(() => Math.random() - 0.5);

La idea: ordenar el arreglo con un comparador que devuelve ±0.5 al azar. La implementación parece ingeniosa; el resultado está sesgado.

El motivo: los ordenamientos por comparación (introsort, mergesort, timsort) llaman al comparador con un patrón estructurado. Con un comparador aleatorio, algunos ordenamientos son más probables que otros. El experimento clásico es mezclar una lista de 5 elementos 100 000 veces de esta forma y contar las ordenaciones resultantes. La distribución es visiblemente no uniforme.

Para un cuestionario de 10 preguntas, el sesgo es invisible. Para la asignación aleatoria de tratamiento en un ensayo clínico, es una cuestión de integridad de la investigación.

La otra mezcla rota — intercambios aleatorios repetidos

// TAMPOCO HAGAS ESTO
for (let k = 0; k < arr.length * 10; k++) {
  const i = Math.floor(Math.random() * arr.length);
  const j = Math.floor(Math.random() * arr.length);
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

«Solo intercambia pares al azar un montón de veces». La convergencia a la distribución uniforme es lenta y nunca está garantizada. Algunos ordenamientos siguen sesgados incluso tras muchas iteraciones. Fisher-Yates hace en n intercambios lo que este enfoque aproxima en 10n intercambios y aun así no logra del todo.

Aleatoriedad criptográfica frente a no criptográfica

El algoritmo de mezcla es correcto, pero la calidad de la fuente de números aleatorios también importa. Dos fuentes en los entornos modernos:

• Math.random() en JS, random.random() en Python. Rápido, determinista dada una semilla, no criptográficamente seguro. Apto para juegos, cuestionarios, aleatorización de muestras.
• crypto.getRandomValues() en JS, secrets.randbelow() en Python. Más lento, pero saca de la fuente aleatoria criptográfica del sistema operativo. Necesario para las mezclas sensibles a la seguridad (lotería, asignación de tratamiento en pruebas A/B, cualquier cosa donde el sesgo se pueda explotar).

La herramienta Mezclar Líneas de TextKit usa crypto.getRandomValues(), así que la salida es criptográficamente uniforme. La mayoría del código de producción en contextos no de seguridad usa la función de la biblioteca estándar (alternativas a Array.prototype.sort(), random.shuffle), que también es apta para usos que no son de seguridad.

Cuándo importa de verdad la calidad de la mezcla

La mayoría de los usos casuales (aleatorizar un cuestionario, mezclar una lista de reproducción para la próxima sesión) no notan las mezclas sesgadas. Tres contextos donde importa:

1. Muestreo estadístico. Si mezclas para extraer una muestra aleatoria, las mezclas sesgadas producen muestras sesgadas. La estadística posterior hereda el sesgo.
2. Validación cruzada. Dividir un conjunto de datos en k pliegues requiere una asignación uniformemente aleatoria a cada pliegue. Mezcla sesgada → desequilibrio de pliegues → estimaciones engañosas del rendimiento del modelo.
3. Asignación de tratamiento en experimentos. Los ensayos controlados aleatorizados requieren una asignación verdaderamente aleatoria. Una mezcla sesgada introduce un factor de confusión difícil de detectar después.

Para estos contextos, usa una implementación de Fisher-Yates conocida y fiable, respaldada por aleatoriedad criptográfica. No escribas la tuya; no confíes en mezclas que no puedas auditar.

Navegador, línea de comandos y Excel

Navegador: la herramienta Mezclar Líneas ejecuta Fisher-Yates con aleatoriedad criptográfica sobre la entrada. Un pegado, copia el resultado.

Línea de comandos de Linux/macOS: shuf input.txt. Una implementación de Fisher-Yates en coreutils. sort -R input.txt también mezcla, con una peculiaridad: agrupa las líneas iguales (una decisión de diseño deliberada por estabilidad). Para «cada línea aleatoria de forma independiente», shuf es la mejor opción.

Excel / Google Sheets: agrega una columna auxiliar con RAND() y ordena por esa columna. Esto es técnicamente el enfoque roto de «ordenar por una clave aleatoria», pero el orden de Excel es lo bastante estable y determinista como para que el sesgo sea pequeño en el uso típico.

El resumen en dos líneas

Usa Fisher-Yates. Si la herramienta que usas no dice qué algoritmo usa, asume que es el equivocado y usa una que sí lo diga.

Para el artículo compañero sobre ordenar, mira cómo ordenar líneas alfabéticamente. Para la referencia más amplia sobre las operaciones con listas, mira operaciones con listas: la guía completa.