Una permutación aleatoria es un ordenamiento aleatorio de un conjunto de objetos, es decir, una variable aleatoria con valor de permutación . El uso de permutaciones aleatorias es común en juegos de azar y en algoritmos aleatorios en teoría de codificación , criptografía y simulación . Un buen ejemplo de una permutación aleatoria es la mezcla justa de una baraja de cartas estándar : esta es idealmente una permutación aleatoria de las 52 cartas.
Un algoritmo para generar una permutación aleatoria de un conjunto de tamaño n de manera uniforme y aleatoria , es decir, de manera que cada una de las n permutaciones tenga la misma probabilidad de aparecer, consiste en generar una secuencia seleccionando aleatoriamente de manera uniforme un número entero entre 1 y n (inclusive), secuencialmente y sin reemplazo n veces, y luego interpretar esta secuencia ( x 1 , ..., x n ) como la permutación
se muestra aquí en notación de dos líneas .
Un método de fuerza bruta ineficiente para el muestreo sin reemplazo podría seleccionar entre los números entre 1 y n en cada paso, reintentando la selección cada vez que el número aleatorio elegido sea una repetición de un número ya seleccionado hasta seleccionar un número que aún no haya sido seleccionado. El número esperado de reintentos por paso en tales casos escalará con el inverso de la fracción de números ya seleccionados, y el número total de reintentos como la suma de esos inversos, lo que hace que este sea un enfoque ineficiente.
Estos reintentos se pueden evitar utilizando un algoritmo en el que, en cada i- ésimo paso cuando ya se han elegido x 1 , ..., x i − 1 , se elige un número aleatorio uniforme j entre 1 y n − i + 1 (inclusive) y se establece x i igual al j -ésimo mayor de los números que aún no se han seleccionado. Esto selecciona de manera aleatoria uniforme entre los números restantes en cada paso sin reintentos.
Un algoritmo simple para generar una permutación de n elementos de manera uniforme y aleatoria sin reintentos, conocido como el barajado de Fisher-Yates , es comenzar con cualquier permutación (por ejemplo, la permutación identidad ), y luego recorrer las posiciones 0 a n − 2 (usamos una convención donde el primer elemento tiene índice 0 y el último elemento tiene índice n − 1), y para cada posición i intercambiar el elemento que se encuentra allí actualmente con un elemento elegido aleatoriamente de las posiciones i a n − 1 (el final), inclusive. Cualquier permutación de n elementos será producida por este algoritmo con una probabilidad exactamente 1/ n !, produciendo así una distribución uniforme de las permutaciones.
unsigned uniform ( unsigned m ); /* Devuelve un entero aleatorio 0 <= uniform(m) <= m-1 con distribución uniforme */ void initialize_and_permute ( unsigned permutation [], unsigned n ) { unsigned i ; for ( i = 0 ; i <= n -2 ; i ++ ) { unsigned j = i + uniform ( n - i ); /* Un entero aleatorio tal que i ≤ j < n */ swap ( permutation [ i ], permutation [ j ]); /* Intercambia el elemento elegido aleatoriamente con permutation[i] */ } } Si la uniform()función se implementa de forma sencilla como random() % (m)entonces habrá un sesgo en la distribución de permutaciones si el número de valores de retorno de random()no es un múltiplo de m. Sin embargo, este efecto es pequeño si el número de valores de retorno de random()es órdenes de magnitud mayor que m.
Al igual que con todas las implementaciones computacionales de procesos aleatorios, la calidad de la distribución generada por una implementación de un algoritmo aleatorio como la mezcla de Fisher-Yates, es decir, qué tan cerca está la distribución realmente generada de la distribución deseada, dependerá de la calidad de las fuentes subyacentes de aleatoriedad en la implementación, como los generadores de números pseudoaleatorios o los generadores de números aleatorios de hardware . Hay muchas pruebas de aleatoriedad para permutaciones aleatorias, como la prueba de "permutaciones superpuestas" de las pruebas Diehard . Una forma típica de tales pruebas es tomar alguna estadística de permutación para la cual se conoce teóricamente la distribución y luego probar si la distribución de esa estadística en un conjunto de permutaciones generadas aleatoriamente a partir de una implementación se aproxima estrechamente a la distribución de esa estadística de la distribución verdadera.
La distribución de probabilidad para el número de puntos fijos de una permutación aleatoria uniformemente distribuida de n elementos se aproxima a una distribución de Poisson con valor esperado 1 a medida que n crece. [1] Los primeros n momentos de esta distribución son exactamente los de la distribución de Poisson. En particular, la probabilidad de que una permutación aleatoria no tenga puntos fijos (es decir, que la permutación sea un trastorno ) se aproxima a 1/ e a medida que n aumenta.