¿Es correcta la implementación C de la compilación de Fisher-Yates?

Question

Aquí hay una implementación en C de Fisher-Yates que quiero usar en una rutina de barajado de barajas. ¿Estoy haciendo esto correctamente (n = longitud de la matriz)?

Nota: El ciclo do-while intenta corregir el sesgo del módulo (consulte here). Agrega un poco de sobrecarga al procedimiento y podría eliminarse si no le importa el sesgo de bits bajos.

void shuffle(int *array, int n) { 

    int i, j, tmp, upper_bound; 

    srand(time(NULL)); 

    for (i = n - 1; i > 0; i--) { 

    upper_bound = RAND_MAX - ((RAND_MAX % (i + 1)) + 1); 

    do { 
     j = rand() % (i + 1); 
    } while (j > upper_bound); 

    tmp = array[j]; 
    array[j] = array[i]; 
    array[i] = tmp; 
    } 
} 

Answer 1

En primer lugar, se debe extraer el código para generar un número aleatorio que se distribuye por igual entre 0 (ambos inclusive) y n (exclusivo) a una función separada. Esa es una buena tarea de trabajo que necesitarás en otro lugar, también.

En segundo lugar, no llamaría a srand dentro de la función shuffle pero dependerá de la persona que llama al inicializar el generador de números aleatorios. De esa manera puedes barajar un mazo más de una vez en un segundo.

En tercer lugar, debe hacer la prueba para j > upper_bound antes de dividir por i + 1. Es poco probable que i esté cerca de RAND_MAX.

static int rand_int(int n) { 
    int limit = RAND_MAX - RAND_MAX % n; 
    int rnd; 

    do { 
    rnd = rand(); 
    } while (rnd >= limit); 
    return rnd % n; 
} 

void shuffle(int *array, int n) { 
    int i, j, tmp; 

    for (i = n - 1; i > 0; i--) { 
    j = rand_int(i + 1); 
    tmp = array[j]; 
    array[j] = array[i]; 
    array[i] = tmp; 
    } 
} 

Para comprobar si esta aplicación puede ser correcta, es necesario asegurarse de que usted le pidió al generador de números aleatorios para log2(n!) bits de aleatoriedad. En otras palabras, el producto de todos los n s otorgados a la función rand_int debe ser n!.