Esta implementação C do shuffle de Fisher-Yates está correta?

Aqui está uma implementação C de Fisher-Yates que eu quero usar em uma rotina de embaralhamento de baralhos. Estou fazendo isso corretamente (n = comprimento da matriz)?

Nota: O loop do-while tenta corrigir o viés do módulo (veja aqui ). Ele adiciona um pouco de sobrecarga ao procedimento e pode ser eliminado se você não se importar com o viés de baixo bit.

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; } } 

Primeiro, você deve extrair o código para gerar um número random que seja igualmente distribuído entre 0 (inclusive) e n (exclusivo) para uma function separada. Essa é uma boa tarefa que você precisará em outro lugar também.

Segundo, eu não ligaria para o srand dentro da function shuffle , mas dependeria do chamador para inicializar o gerador de números randoms. Dessa forma, você pode embaralhar um baralho mais de uma vez por segundo.

Terceiro, você deve fazer o teste para j > upper_bound antes de dividir por i + 1 . É improvável que i esteja perto 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 verificar se esta implementação pode estar correta, você precisa assegurar que você pediu ao gerador de números randoms por bits de aleatoriedade log2(n!) . Em outras palavras, o produto de todos os n s dados para a function rand_int deve ser n! .