Robię trochę komputerowego wypoczynku rekreacyjnego. Mój mini-projekt był symulacją włoskiej gry „tomboli”. Kluczowym elementem konstrukcyjnym była symulacja następującego procesu;

Gra jest kontrolowana przez mężczyznę z workiem 90 kulek, ponumerowanych od 1 do 90. Losuje on losowo kulki z worka, za każdym razem wywołując wśród graczy numer marmuru.

Po krótkiej myśli napisałem następujący kod dla tego bloku konstrukcyjnego;

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

Wiem, że w symulacji gry z liczbami losowymi są subtelności i pułapki, więc chociaż jestem całkiem zadowolony z mojego kodu, moje zaufanie jest nieco mniejsze niż 100%. Więc moje pytania są;

1) Czy coś jest nie tak z moim kodem?

2) [jeśli odpowiedź na 1) jest nie] Czy nieświadomie korzystam ze standardowego algorytmu tasowania?

3) [jeśli odpowiedź na 2) brzmi nie] Jak mój algorytm porównuje się do standardowych alternatyw?

EDYTOWAĆ Dziękujemy wszystkim, którzy odpowiedzieli. Zamierzam zaakceptować odpowiedź Aidana Cully'ego, ponieważ okazuje się, że odkrywałem na nowo algorytm Fishera-Yatesa i ujawniający to dociera do sedna sprawy. Oczywiście nie jest zaskoczeniem, że mogłem zaoszczędzić czas i wysiłek, wykonując pewne badania z góry. Ale z drugiej strony był to zabawny projekt hobby. Reszta symulacji była rutynowa, to była najciekawsza część, a ja sam pozbawiłbym się przyjemności, bo sam nie musiałem iść. Dodatkowo próbowałem symulować mężczyznę biorącego kulki z torby i było dość późno w tym kawałku, że zdałem sobie sprawę, że sytuacja była dokładnie analogiczna do tasowania kart.

Kolejny interesujący jest fakt, że istnieje mała wada, zidentyfikowana przez Kena, który podkreśla, że ​​często powtarzany wzór rand ()% N nie jest dobrym sposobem na wybranie losowej liczby z zakresu 0..N-1.

Wreszcie w mojej wersji Fisher-Yates brakuje eleganckiej sztuczki, która pozwala na ładną właściwość tasowania na miejscu. W rezultacie mój algorytm skończyłby się równie losowym, ale odwróconym tasowaniem.