Ich habe ein wenig Freizeiturlaubsberechnung gemacht. Mein Mini-Projekt war eine Simulation des italienischen Spiels "Tomboli". Ein Schlüsselbaustein war eine Simulation des folgenden Prozesses;

Das Spiel wird von einem Mann mit einer Tüte mit 90 Murmeln, nummeriert von 1 bis 90, gesteuert. Er zieht nach dem Zufallsprinzip Murmeln aus der Tüte und ruft den Spielern jedes Mal die Marmornummer zu.

Nach einigem Überlegen habe ich den folgenden Code für diesen Baustein geschrieben;

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

Ich weiß, dass es in der Spielsimulation überall Feinheiten und Fallen mit Zufallszahlen gibt. Obwohl ich mit meinem Code ziemlich zufrieden bin, ist mein Selbstvertrauen etwas weniger als 100%. Meine Fragen sind also:

1) Stimmt etwas mit meinem Code nicht?

2) [wenn die Antwort auf 1) nein ist] Benutze ich unwissentlich einen Standard-Mischalgorithmus?

3) [wenn die Antwort auf 2) nein ist] Wie vergleicht sich mein Algorithmus mit Standardalternativen?

BEARBEITEN Vielen Dank an alle, die geantwortet haben. Ich werde die Antwort von Aidan Cully akzeptieren, da sich herausstellt, dass ich den Fisher-Yates-Algorithmus wiederentdeckt habe und dies auf den Punkt gebracht habe. Natürlich ist es keine Überraschung, dass ich mir durch Recherchen im Vorfeld Zeit und Mühe hätte sparen können. Aber andererseits war es ein lustiges Hobbyprojekt. Der Rest der Simulation war Routine, dies war der interessanteste Teil, und ich hätte mir den Spaß genommen, wenn ich nicht selbst versucht hätte. Außerdem habe ich versucht, einen Mann zu simulieren, der Murmeln aus einer Tüte nimmt, und es war ziemlich spät in dem Stück, als mir klar wurde, dass die Situation für das Mischen von Karten genau analog war.

Ein weiterer interessanter Punkt ist, dass es einen kleinen Fehler gibt, der von Ken identifiziert wurde, der darauf hinweist, dass das oft wiederholte Muster rand ()% N keine wirklich gute Möglichkeit ist, eine Zufallszahl aus dem Bereich 0..N-1 auszuwählen.

Schließlich fehlt meiner Version von Fisher-Yates der elegante Trick, der die nette Eigenschaft des Mischens ermöglicht. Infolgedessen würde mein Algorithmus ein ebenso zufälliges, aber umgekehrtes Mischen ergeben.