STL Zufälle

Martin Kompf

Wenn der Zufall bei der Programmausführung eine Rolle spielen soll, dann kann der STL-Algorithmus random_shuffle Anwendung finden.

Bereits im Artikel Zufallszahlen wurde auf die Bedeutung zufällig erzeugter Zahlen hingewiesen. Die dort vorgestellte Methode benutzt die Funktion rand() aus der Standard C Library zur Erzeugung von Zufallszahlen.

Die Grenzen

Dieses einfache Verfahren liefert in einigen Situationen allerdings unbefriedigende Ergebnisse: So erzeugt rand() Zufallszahlen im Wertebereich [0, RAND_MAX). Will man die Funktion beispielsweise einsetzen, um das Durchmischen eines Skatspiels zu simulieren, dann benötigt man Zahlen aus dem Bereich [1, 32]. Der Wertebereich kann zwar, wie in der Funktion irand() aus Zufallszahlen dargestellt, eingeschränkt werden. Jedoch ist auf diese Art und Weise noch nicht sichergestellt, dass in der erzeugten Zahlenfolge jede Zahl von 1 bis 32 genau einmal vorkommt (also nur die Reihenfolge zufällig ist). Außerdem lassen sich auf diese Art und Weise nur zufällige Zahlen erzeugen. Die Methode kann ohne weiteres nicht zur Erzeugung einer zufälligen Reihenfolge allgemeiner Objekte benutzt werden.

Ein Ausweg

In dieser Situation hilft der in der STL vorhandene Algorithmus random_shuffle weiter. Dieser bringt die Elemente in einem übergebenen Bereich in eine zufällige Reihenfolge.

Im ersten Beispiel wollen wir das Durchmischen eines Skatspiels simulieren. Dafür werden die Zahlen von 1 bis 32 (die hier für die einzelnen Spielkarten stehen) in eine zufällige Reihenfolge gebracht:

#include <algorithm>
#include <iostream>
#include <iterator>
using namespace std;

int main()
{
    const int a_size = 32;
    int a[a_size];
    int i;
 
    for (i = 0; i < a_size; ++i) a[i] = i + 1;
  
    random_shuffle( a, a + a_size);
    copy( a, a + a_size, ostream_iterator<int>(cout, " "));
    cout << endl;
}

random_shuffle bekommt als Parameter also die Zeiger auf den Anfang und hinter das Ende des zu durchmischenden Bereichs übergeben.

Universeller Algorithmus

Dieses Verfahren lässt sich natürlich auch auf beliebige Objekte in STL Containern anwenden. Im folgenden Beispiel wollen wir eine zufällige Reihenfolge von Wochentagen erzeugen und ausgeben. Die Namen der Wochentage werden dazu zunächst in einen Vektor gepackt und dann mittels random_shuffle durchmischt:

#include <vector>
#include <string>
//...
 
    vector<string> wd;
    wd.push_back("Montag");
    wd.push_back("Dienstag");
    wd.push_back("Mittwoch");
    wd.push_back("Donnerstag");
    wd.push_back("Freitag");
    wd.push_back("Sonnabend");
    wd.push_back("Sonntag");
 
    random_shuffle( wd.begin(), wd.end());
    copy( wd.begin(), wd.end(), ostream_iterator<string>(cout, "\n"));

Wird das Programm mehrmals hintereinander ausgeführt, so stellen wir fest, dass zwar eine zufällige, aber jedesmal die gleiche Folge von Zahlen bzw. Wochentagen ausgegeben wird. Das liegt im Verhalten des verwendeten STL-internen Zufallsgenerator begründet. Dieser wird bei jedem Programmstart immer mit dem gleichen Startwert (dem Seed) versorgt. Eine Möglichkeit, den Seed explizit - analog zu srand() - zu setzen, besteht nicht. Jedoch bietet random_shuffle die Möglichkeit, einen eigenen Zufallsgenerator (der dann beliebig »geseedet« werden könnte) zu verwenden. Um dieses Feature benutzen zu können, müssen wir uns zunächst mit dem Prinzip der functors aus der STL befassen - dazu mehr im nächsten Artikel!

Links zum Thema:

Weitere interessante Artikel: