Permutaciones aleatorias

01 · Punto de partida

Sortear uno es fácil; mezclar todos, no

El Tema 23 sortea un ganador con choice. Pero repartir un mazo, ordenar un examen o rotar una playlist exigen todos los elementos en orden aleatorio: una permutación donde cada uno de los n! órdenes tenga prob. 1/n!. El atajo “recorro y cambio cada carta con otra al azar” parece funcionar y vicia el mazo: algunas órdenes salen el doble que otras.

La solución es de 1938 (Fisher-Yates, 1964 Knuth): ir fijando desde el final con un sorteo que se achica j ∈ 0…i. Tres líneas, O(n), parejo demostrable.

• ¿Por qué j va de 0…i y no de 0…n−1?
• ¿Cuántos órdenes parejos hay con n = 4?
• ¿Qué tiene de malo ordenar por clave aleatoria?
• ¿Por qué shuffle no devuelve nada?

02 · Definición

n! órdenes, una sola receta pareja

03 · Técnica correcta

El rango manda

Con n = 3 el naive hace 3³ = 27 caminos sobre 6 órdenes: 27 no es múltiplo de 6, así que es imposible repartir parejo (unas salen 5/27, otras 4/27). Fisher-Yates hace 3·2·1 = 6 caminos: biyección perfecta con los 6 órdenes.

j ≤ i siempre

El error clásico es randint(0, n−1) en cada paso. Lo correcto: randint(0, i) con i decreciente. Un carácter de diferencia, sesgo total.

Entero sin % viciado

El j debe ser parejo en 0…i: con fuente entera usar rechazo si hay resto (Tema 22) o floor sobre u (Tema 19).

shuffle muta

random.shuffle(mazo) mezcla in-place y devuelve None: m = shuffle(m) deja m = None. Para copiar: sample(mazo, len(mazo)).

04 · Ejemplos

Tres mezclas típicas

1. 1
   Mazo de 52.

   shuffle(mazo) con semilla registrada: 51 sorteos, 8e67 órdenes parejos.

2. 2
   Examen de 10 preguntas.

   Cada alumno recibe una permutación distinta: sin ventaja de posición.

3. 3
   Playlist sin “siempre primero lo mismo”.

   Mezcla completa O(n) una vez, no choice repetido (que repite temas, Tema 23).

05 · Implementación en Python

Fisher-Yates a mano y conteo 1/n!

Implementamos FY con randrange(i+1) y verificamos con n = 3: las 6 permutaciones rondan 1/6 en 6000 mezclas. El naive no lo logra.

import random
from collections import Counter

def fisher_yates(xs, rng):
    a = list(xs)
    for i in range(len(a) - 1, 0, -1):
        j = rng.randrange(i + 1)
        a[i], a[j] = a[j], a[i]
    return a


rng = random.Random(24)
c = Counter(tuple(fisher_yates("ABC", rng)) for _ in range(6000))
for perm, n in sorted(c.items()):
    print("".join(perm), round(n / 6000, 4))

Seis valores ≈ 0,1667: biyección 6 caminos → 6 órdenes.

El naive se delata

import random
from collections import Counter

def naive(xs, rng):
    a = list(xs)
    n = len(a)
    for i in range(n):
        j = rng.randrange(n)
        a[i], a[j] = a[j], a[i]
    return a


rng = random.Random(24)
c = Counter(tuple(naive("ABC", rng)) for _ in range(6000))
for perm, n in sorted(c.items()):
    print("".join(perm), round(n / 6000, 4))

06 · Exploración

Laboratorio: 6 órdenes bajo lupa

Con n = 3 hay 6 permutaciones: las barras deben rondar 1/6. Compará Fisher-Yates con el naive: el naive deja dos barras altas sistemáticas (5/27 frente a 4/27). Subí los ensayos: el sesgo no se diluye.

La línea es 1/6 ≈ 0,1667. Barras naranjas sistemáticamente altas = órdenes favorecidos por el algoritmo.

Preguntas para explorar

1. Con naive y 12000 ensayos: ¿el χ² se achica o crece? ¿Qué dice de sesgo vs ruido?
2. ¿Qué dos órdenes favorece el naive? ¿Coinciden con la teoría 5/27?
3. Si mezclaras un mazo de 52 con naive, ¿detectarías el sesgo contando? ¿Por qué no?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: mazo de 52

Mezclá un mazo con shuffle y verificá que están las 52 cartas sin repetidos ni faltantes.

import random

mazo = [f"{v}{p}" for v in "A23456789JQK" for p in "♠♥♦♣"]
rng = random.Random(10)
rng.shuffle(mazo)
print(mazo[:5], len(mazo), len(set(mazo)))

Ejercicio 2: medir el naive

Repetí el conteo del naive con 30000 ensayos y comprobá el 5/27 ≈ 0,1852 en los favorecidos.

import random
from collections import Counter

def naive(xs, rng):
    a = list(xs)
    for i in range(len(a)):
        j = rng.randrange(len(a))
        a[i], a[j] = a[j], a[i]
    return a


rng = random.Random(24)
c = Counter(tuple(naive("ABC", rng)) for _ in range(30000))
print(sorted((round(n / 30000, 4) for n in c.values())))

Ejercicio 3: copia sin mutar

Devolvé una mezcla nueva sin tocar la original de dos formas: FY manual y sample.

import random

orig = list("ABCDE")
rng = random.Random(2)
fy = list(orig)
for i in range(len(fy) - 1, 0, -1):
    j = rng.randrange(i + 1)
    fy[i], fy[j] = fy[j], fy[i]
otra = rng.sample(orig, len(orig))
print(orig, fy, otra)

09 · Síntesis

Ideas para recordar

En el próximo tema tomaremos porciones: muestreo aleatorio con y sin reemplazo.