Pregunta : ¿Alguien tiene una prueba matemática precisa de El algoritmo de Durstenfeld ?
La primera $O(n)$ shuffle o generador de permutación aleatoria fue publicado por Richard Durstenfeld en 1964. Este algoritmo llegó a la atención de los programadores porque fue incluido en Knuth 1969, página 125, 2 como Algoritmo P . Una declaración sucinta del algoritmo es: \begin {ecuación} \text para \leftarrow N, N-1, \ldots ,2\ \text y que no se puede hacer \begin {Casos} \text {Elija al azar un número} {\a6} {\a6} \in [1,k] \\ \text {Intercambio } \pi [r] \text y \pi [k],\ \end {Casos} \end {ecuación} donde $ \pi [1 \ldots n]$ es la matriz que debe ser barajada o cambiada aleatoriamente.
Este es un algoritmo realmente elegante, computacional y matemáticamente. Computacionalmente maneja operaciones de conjunto dividiendo la matriz $ \pi $ en un un set sin estrujar $ \pi [1, \ldots , k]$ y un conjunto barajado $ \pi [k+1, \ldots , n]$ . En cada iteración $k$ elige un elemento aleatorio $ \pi [r]$ del set sin batidores $ \pi [1, \ldots , k]$ y la intercambia con $ \pi [k]$ . Esto se mueve $ \pi [r]$ en el nuevo conjunto barajado $ \pi [k, \ldots , n]$ donde permanece, sin moverse, para todas las iteraciones subsiguientes. Esto se hace en $O(1)$ el tiempo y el espacio. Así, la complejidad temporal y espacial del algoritmo de Durstenfeld es $O(n)$ que es óptimo.
Matemáticamente, el algoritmo es elegante porque utiliza implícitamente el conocido lema que cada permutación $ \pi $ es un producto de transposiciones. En cada iteración $k$ el algoritmo elige un número aleatorio $r_k \in [1, \ldots ,k]$ y realiza una transposición $( \pi [k], \pi [r_k])$ . Por lo tanto, la permutación aleatoria producida puede escribirse como
$$ \pi = ( \pi [n], \pi [r_n])( \pi [n-1], \pi [r_{n-1}]) \cdots ( \pi [k], \pi [r_k]) \cdots ( \pi [2], \pi [r_2]), $$
donde $( \pi [k], \pi [r_k])$ es la transposición o el intercambio de $ \pi [k]$ y $ \pi [r_k]$ .
Implementación en Matlab del Algoritmo de Durstenfeld
function p = GRPdurG(p)
% -------------------------------------------------------------
% Randomly permute the elements of p(1:n) using Durstenfeld's
% Random Permutation Algorithm, CACM, Vol 7, No. 7, 1964.
% See Knuth, Section 3.4.2, TAOCP, Vol 2, 3rd Ed.
% Derek O'Connor, 8 Dec 2010. derekroconnor@eircom.net
%
% USE: n=10^7; p = 1:n; p = GRPdur(p);
% -------------------------------------------------------------
n = length(p);
for k = n:-1:2
r = 1+floor(rand*k); % random integer between 1 and k
t = p(k);
p(k) = p(r); % Swap(p(r),p(k)).
p(r) = t;
end
% GRPdurGUn enigma combinatorio
Una permutación aleatoria de los números enteros $\{1,2, \ldots ,10^7\}$ puede ser generado en unos pocos segundos usando el algoritmo Durstenfeld Shuffle en un PC estándar. El espacio combinatorio $ \mathcal {C}$ en este caso es un conjunto de todas las permutaciones de tamaño $10^7$ . El tamaño de este espacio de muestra es \begin {ecuación*} | \mathcal {C}| = n! = (10^7)! \approx 10^{65,657,059} \end {ecuación*} Este es un número gigantesco y está muy por encima de los límites de cualquier generador de números aleatorios conocido. Es decir, $| \mathcal {C}| \ggg | \mathcal {G}|$ el espacio de estado del generador de números aleatorios. Por ejemplo, el período (tamaño del espacio de estado) del conocido Mersenne Twister RNG (MT) se trata de $10^{6000}$ . Por lo tanto, los generadores de permutaciones aleatorias que usan MT deben perder casi todas las permutaciones en este espacio.
No menos, la función de Matlab de arriba produce permutaciones aleatorias de la longitud $10^7$ en las proporciones estadísticas correctas, por ejemplo, $1/e$ son desquiciados, $1/n$ son ciclos, etc., pero debe perder la mayoría de las permutaciones posibles. De ahí el enigma. La pregunta más importante para mí es:
¿Los generadores de permutaciones aleatorias toman muestras uniformes del espacio de las permutaciones ?
asumiendo que usan el mejor generador de números aleatorios disponible. Sospecho que es un problema matemático difícil.
Mira esta discusión de Matlab: ¿Qué echa de menos RANDPERM?
Nota histórica
Creo que el algoritmo de Durstenfeld fue atribuido incorrectamente a Fisher y Yates por Knuth, en (2) abajo. Vea aquí Nota de O'Connor sobre Fisher-Yates . El algoritmo original de Durstenfeld está aquí: Algoritmo del MCCA
Referencias
- Durstenfeld, R. 1964: Algoritmo ACM 235: Permutación aleatoria, Comunicaciones de la ACM Vol 7, No 7.
- Knuth, D. 1969, 1998: Algoritmos seminuméricos 1ª y 3ª Edición. El arte de la computación Serie de programación Volumen 2.
