Verificare algoritmo di riordino Knuth è imparziale possibile

Question

Sono l'attuazione di un progetto di Knuth Shuffle per un C ++ Sto lavorando a. Sto cercando di ottenere i risultati più imparziali dal mio shuffle (e io non sono un esperto di (pseudo) generazione di numeri casuali). Voglio solo per assicurarsi che questo è l'implementazione riordino più imparziale.

draw_t è un tipo di byte (typedef'd a unsigned char). items è il numero di elementi nella lista. Ho incluso il codice per random::get( draw_t max ) qui sotto.

for( draw_t pull_index = (items - 1); pull_index > 1; pull_index-- )
{
    draw_t push_index = random::get( pull_index );

    draw_t push_item = this->_list[push_index];
    draw_t pull_item = this->_list[pull_index];

    this->_list[push_index] = pull_item;
    this->_list[pull_index] = push_item;
}

La funzione random che sto usando è stato modificato per eliminare modulo pregiudizi . RAND_MAX è assegnato a random::_internal_max.

draw_t random::get( draw_t max )
{
    if( random::_is_seeded == false )
    {
        random::seed( );
    }

    int rand_value = random::_internal_max;
    int max_rand_value = random::_internal_max - ( max - ( random::_internal_max % max ) );

    do
    {
        rand_value = ::rand( );
    } while( rand_value >= max_rand_value );

    return static_cast< draw_t >( rand_value % max );
}

Answer 1

Beh, una cosa si potrebbe fare come un test black-box è prendere un po 'di dimensione relativamente piccola matrice, eseguire un gran numero di mescolamenti su di esso, contate quante volte si osserva ogni permutazione, e quindi eseguire prova Chi-quadro di Pearson per determinare se i risultati sono distribuiti uniformemente sopra lo spazio di permutazione.

D'altra parte, il riordino Knuth, AKA il riordino Fisher-Yates, è dimostrato di essere imparziale finché il generatore di numeri casuali che gli indici provengono dal è imparziale.

Answer 2

Se vedo che a destra, il vostro random::get (max) non include max.

Questa riga:

draw_t push_index = random::get( pull_index );

quindi produce un "classico" off-by-one errore, come il tuo pull_index e push_index erroneamente non può mai essere la stessa. Questo produce una polarizzazione sottile che non si può mai avere una voce in cui era prima della riproduzione casuale. In un esempio estremo, le liste a due voci in questo "shuffle" sarebbero sempre essere invertiti.

Answer 3

Date un'occhiata a questo articolo di Jeff Atwood:

Mischiare le carte
http://www.codinghorror.com/blog/archives/001008.html

Vedi anche:

Il pericolo di ingenuità
http://www.codinghorror.com/blog/archives/001015.html

Answer 4

Il Knuth Shuffle stesso è dimostrabilmente imparziale: esiste esattamente un serie di operazioni che produce ogni possibile shuffle. E 'improbabile che il vostro PRNG ha abbastanza bit di stato per esprimere ogni possibile shuffle, tuttavia, in modo la vera domanda è se il PRNG è 'abbastanza casuale' per quanto riguarda il set di mescolamenti sarà effettivamente produrre, e se la vostra strategia di semina è abbastanza sicura .

Solo tu puoi decidere questo, in quanto dipende dalle conseguenze di un riordino che non è abbastanza casuale. Se hai a che fare con denaro reale, ad esempio, vorrei suggerire il passaggio ad un PRNG crittograficamente sicuro e migliorare la vostra strategia di semina. Sebbene la maggior parte costruita nel PRNGs generare buoni casualità, ma sono anche abbastanza facile da decodificare, e semi di vocazione () senza argomenti è probabile semina in base al tempo attuale, che è abbastanza facile da prevedere.

Answer 5

#include <cstdlib> // srand() && rand()

/** Shufle the first 'dim' values in array 'V[]'.
    - Implements the Fisher–Yates_shuffle.
    - Uses the standard function 'rand()' for randomness.
    - Initialices the random sequence using 'seed'.
    - Uses 'dim' swaps.
    \see http://stackoverflow.com/questions/1685339/
    \see http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm
*/
template <class T>
void Fisher_Yates_shuffle( T* V, unsigned dim , unsigned seed ) {
    srand(seed);
    T temp;
    unsigned i,iPP;

    i   = dim-1;
    iPP = dim;
    while ( i>0 ) {
        unsigned j = rand() % iPP;
        if ( i!=j ) { // swap
            temp = V[i]; V[i] = V[j]; V[j] = temp;
        }
        iPP = i;
        --i;
    }
/*
    This implementation depends on the randomness of the random number
    generator used ['rand()' in this case].
*/
}