Fisher Yates variación

Question

El clásico de Fisher Yates es como la siguiente:

void shuffle1(std::vector<int>& vec) 
{ 
    int n = vec.size(); 
    for (int i = n - 1; i > 0; --i) 
    { 
     std::swap(vec[i], vec[rand() % (i + 1)]); 
    } 
} 

Ayer, he implementado la iteración "hacia atrás" por error:

void shuffle2(std::vector<int>& vec) 
{ 
    int n = vec.size(); 
    for (int i = 1; i < n; ++i) 
    { 
     std::swap(vec[i], vec[rand() % (i + 1)]); 
    } 
} 

¿Es esta versión de ninguna manera peor (o mejor) que el primero? ¿Distorsiona las probabilidades resultantes?

Answer 1

Sí, es una distribución uniforme asumiendo rand() es. Lo demostraremos mostrando que cada entrada puede generar cada permutación con la misma probabilidad.

N = 2 se puede probar fácilmente. Vamos a dibujar como un árbol donde los niños representan cada cadena se puede obtener mediante la inserción del carácter tras la coma en la cadena de más a la izquierda.

0,1 //input where 0,1 represent indices 
01 10 //output. Represents permutations of 01. It is clear that each one has equal probability 

Para N, que tendrá todas las permutaciones de N-1, y el trueque de azar del último carácter de N

(N-1 0th permutation),N  .....   (N-1 Ith permutation),N ________________________ 
    /   \      /     \        \ 
0th permutation of N 1st permutation.... (I*N)th permutation ((I*N)+1)th permutation .... (I*N)+(I-1)th permutation 

Esta inducción de mierda que debe conducir a que tiene una distribución uniforme.

---

Ejemplo:

N = 2:

0,1 
01 10 // these are the permutations. Each one has equal probability 

N = 3:

  0,1|2   // the | is used to separate characters that we will insert later 
    01,2   10,2 // 01, 10 are permutations from N-1, 2 is the new value 
210 021 012 201 120 102 // these are the permutations, still equal probability 

N = 4: (curvada para ayudar a la lectura)

              0,1|23 

                 01,2|3 10,2|3 

              012,3 021,3 210,3 102,3 120,3 201,3 


            1203 1230 1302 3201 
             2103 2130 2301 3102 1023 1032 1320 3021 

etc

Answer 2

se ve bien para mí (suponiendo rand()% N es imparcial, que no lo es). Parece que debería ser posible demostrar que cada permutación de entrada se produce con exactamente 1 secuencia de elecciones aleatorias, donde cada opción aleatoria está equilibrada.

Compare esto con una aplicación defectuosa, como

for (int i = 0; i < v.size(); ++i) { 
    swap(v[i], v[rand() % v.size()]); 
} 

Aquí se puede ver que hay n ⁿ formas igualmente probable que produzca n! permutaciones, y, como n ⁿ no es divisible por n! donde n> 2, algunas de esas permutaciones deben producirse con más frecuencia que otras.