Eu tenho feito um pouco de computação recreativa de férias. Meu mini-projeto foi uma simulação do jogo italiano de "tomboli". Um bloco de construção fundamental foi uma simulação do seguinte processo;

O jogo é controlado por um homem com um saco de 90 bolinhas, numeradas de 1 a 90. Ele desenha bolinhas uma a uma aleatoriamente da sacola, cada vez chamando o número de bolinhas para os jogadores.

Depois de pensar um pouco, escrevi o seguinte código para esse bloco de construção;

// NBR marbles, numbered 1...NBR are in a bag. Simulate randomly
//  pulling them from the bag, one by one, until the bag is empty
void bag( int random_sequence[NBR] )
{
    int i;

    // Store each marble as it is pulled out
    int *store = random_sequence;

    // Array of marbles still in the bag
    int not_yet_pulled[NBR];
    for( i=0; i<NBR; i++ )
        not_yet_pulled[i] = i+1;    // eg NBR=90; 1,2,3 ... 90

    // Loop pulling marbles from the bag, one each time through
    for( i=NBR; i>=1; i-- )
    {
        int x = rand();
        int idx = x%i;  // eg i=90 idx is random in range 0..89
                        // eg i=89 idx is random in range 0..88
                        //            ...
                        // eg i=1  idx is random in range 0..0
                        //    (so we could optimize when i=1 but not worth the bother)
        *store++  = not_yet_pulled[idx];

        // Replace the marble just drawn (so it cannot be pulled again)
        //     with the last marble in the bag. So;
        //     1) there is now one less marble in the bag
        //     2) only marbles not yet pulled are still in the bag
        // If we happened to pull the last marble in the *current subarray*, this is
        //    not required but does no harm.
        not_yet_pulled[idx] = not_yet_pulled[i-1];
    }
}

Eu sei que há sutilezas e armadilhas em todo o lugar na simulação do jogo com números aleatórios, por isso, embora eu esteja muito feliz com o meu código, minha confiança é um pouco menor que 100%. Então minhas perguntas são;

1) Há algo de errado com o meu código?

2) [se a resposta para 1) não é] Estou sem saber usando um algoritmo de embaralhamento padrão?

3) [se a resposta a 2) não for] Como meu algoritmo se compara a alternativas padrão?

EDITAR Obrigado a todos que responderam. Eu vou aceitar a resposta de Aidan Cully porque descobri que eu estava redescobrindo o algoritmo de Fisher-Yates, e revelar isso chega ao cerne da questão. É claro que não é surpresa que eu pudesse ter economizado tempo e esforço fazendo algumas pesquisas iniciais. Mas por outro lado, foi um divertido projeto de passatempo. O resto da simulação era rotineiro, essa era a parte mais interessante, e eu teria me privado de prazer por não ter ido eu mesmo. Além disso, eu estava tentando simular um homem tirando bolinhas de gude de uma sacola, e era bem tarde na peça que percebi que a situação era exatamente análoga a embaralhar cartas.

Outro ponto de interesse é que existe uma pequena falha, identificada por Ken, que aponta que o padrão repetido freqüentemente rand ()% N não é uma maneira realmente boa de escolher um número aleatório no intervalo 0..N-1.

Finalmente, minha versão de Fisher-Yates não tem o truque elegante que permite a boa propriedade de embaralhar no lugar. Como resultado, meu algoritmo acabaria com um shuffle igualmente aleatório, mas invertido.