Verifique o algoritmo Knuth Shuffle é o mais imparcial possível

Question

Estou implementando um Knuth Shuffle Para um projeto C ++ em que estou trabalhando. Estou tentando obter os resultados mais imparciais do meu shuffle (e não sou especialista em geração de números aleatórios (pseudo)). Eu só quero garantir que essa seja a implementação mais imparcial do Shuffle.

draw_t é um tipo de byte (typedef'D para unsigned char). items é a contagem de itens na lista. Eu incluí o código para random::get( draw_t max ) abaixo de.

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

A função aleatória que estou usando foi modificada para eliminar Viés de módulo. RAND_MAX é atribuído 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

Bem, uma coisa que você pode fazer como teste de caixa preta é levar um tamanho de matriz relativamente pequeno, realizar um grande número de shuffles, conte quantas vezes você observa cada permutação e depois executa O qui-quadrado de Pearson Teste para determinar se os resultados são distribuídos uniformemente pelo espaço de permutação.

Por outro lado, o Knuth Shuffle, também conhecido como The Fisher-Yates Shuffle, é comprovado que é imparcial, desde que o gerador de números aleatórios de onde os índices sejam imparciais.

Answer 2

Se eu vejo isso certo, seu random::get (max) não inclui max.

Está linha:

draw_t push_index = random::get( pull_index );

Em seguida, produz um erro "clássico" fora por um, como seu pull_index e push_index erroneamente nunca pode ser o mesmo. Isso produz um viés sutil que você nunca pode ter um item onde estava antes do Shuffle. Em um exemplo extremo, as listas de dois itens nesse "shuffle" sempre seriam revertidas.

Answer 3

Have a look at this article from Jeff Atwood:

Shuffling
http://www.codinghorror.com/blog/archives/001008.html

See also:

The Danger of Naïveté
http://www.codinghorror.com/blog/archives/001015.html

Answer 4

The Knuth shuffle itself is provably unbiased: There exists exactly one series of operations that yields each possible shuffle. It's unlikely your PRNG has enough bits of state to express every possible shuffle, however, so the real question is if your PRNG is 'random enough' with regards to the set of shuffles it will actually produce, and whether your seeding strategy is secure enough.

Only you can decide this, as it depends on the consequences of a shuffle that isn't random enough. If you're dealing with real money, for example, I would suggest switching to a cryptographically secure PRNG and improving your seeding strategy. Although most built in PRNGs generate good randomness, they're also quite easy to reverse engineer, and calling seed() with no arguments is likely seeding based on the current time, which is pretty easy to predict.

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].
*/
}