L'implementazione C di Fisher-Yates shuffle è corretta?

Question

Ecco una implementazione C di Fisher-Yates che voglio usare in una routine di mescolamento del mazzo. Sto facendo questo correttamente (n = lunghezza della matrice)?

Nota: il ciclo do-while tenta di correggere il bias del modulo (vedere here). Aggiunge un po 'di overhead alla procedura e potrebbe essere eliminato se non ti interessa il bias a basso 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; 
    } 
} 

Answer 1

In primo luogo, è necessario estrarre il codice per la generazione di un numero casuale che è equamente distribuito tra 0 (incluso) e n (esclusiva) per una funzione separata. È un bel lavoro che ti servirà anche altrove.

In secondo luogo, non chiamerei srand all'interno della funzione shuffle ma dipende dal chiamante all'inizializzazione del generatore di numeri casuali. In questo modo puoi mescolare un mazzo più di una volta in un secondo.

In terzo luogo, è necessario eseguire il test per j > upper_bound prima di dividere per i + 1. È improbabile che i sia mai vicino a 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; 
    } 
} 

Per verificare se questa implementazione può essere corretto, è necessario assicurarsi che lei ha chiesto il generatore di numeri casuali per log2(n!) bit di casualità. In altre parole, il prodotto di tutti gli n s assegnati alla funzione rand_int deve essere n!.