¿Es correcta esta implementación en C de la reproducción aleatoria de Fisher-Yates?
Aquí hay una implementación en C de Fisher-Yates que quiero usar en una rutina de barajado de mazos. ¿Estoy haciendo esto correctamente (n = longitud de la matriz)?
Nota: El bucle do- while intenta corregir el sesgo del módulo (consulte aquí ). 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;
}
}
Primero, debes extraer el código para generar un número aleatorio que se distribuya equitativamente entre 0(inclusive) y n(exclusivo) en una función separada. Es una buena tarea de trabajo que también necesitarás en otros lugares.
En segundo lugar, no llamaría sranddentro de la shufflefunción, sino que dependería de que la persona que llama inicialice el generador de números aleatorios. De esa manera puedes barajar un mazo más de una vez por segundo.
En tercer lugar, debes hacer la prueba j > upper_boundantes de dividir por i + 1. Es poco probable que eso iesté cerca alguna vez 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 implementación puede ser correcta, debe asegurarse de haber solicitado log2(n!)bits de aleatoriedad al generador de números aleatorios. En otras palabras, el producto de todos los ns dados a la rand_intfunción debe ser n!.
