¿Cómo ordenar aleatoriamente una secuencia de forma eficaz y sencilla?

Question

Permítanme preguntar si mi algoritmo simple instantánea tiene graves defectos ,para el uso de criptografía, o no. Que se supone que al azar cambiar el orden en una secuencia dada S[1..n] de la longitud n. Supongamos que tengo un buen generador de números aleatorios random() que devuelve un entero aleatorio en el rango [1..n].

while true
  for i in 1..n
    r=random()
    swap S[i] and S[r]

Si no tiene fallos graves, ¿cuándo puedo terminar el bucle while? ¿Hay algún algoritmo conocido que también sea fácil de escribir en un programa de ordenador?

Gracias de antemano.

Answer 1

El algoritmo que sugieres no te dará una distribución uniforme, así que supongo que no es realmente lo que quieres. Una razón simple es que hay $n^n$ ejecuciones posibles e igualmente probables del algoritmo (se elige un número aleatorio en $[1..n]$ y lo haces $n$ veces), mientras que hay $n!$ diferentes permutaciones. Dado que $n! \not | \ \ n^n$ es seguro que algunas permutaciones tendrán más posibilidades de ser elegidas (aunque no tengo ni idea de cuáles son).

Los enlaces proporcionados por Rahul Narain le remitirán a las fuentes adecuadas.