Laden...

[Snippet] Zufallszahlen, die sich nicht wiederholen

Erstellt von herbivore vor 16 Jahren Letzter Beitrag vor 16 Jahren 15.405 Views
herbivore Themenstarter:in
49.485 Beiträge seit 2005
vor 16 Jahren
[Snippet] Zufallszahlen, die sich nicht wiederholen

Beschreibung:

Eine einfache, schnelle und zuverlässige Methode, um Zufallszahlen zu erzeugen, die sich nicht wiederholen, ist eine Liste mit den Ausgangszahlen zufällig zu mischen und anschließend diese Liste sequentiell durchzugehen.

Wenn man z.B. Zufallszahlen zwischen 0-9 ohne Wiederholung haben möchte, erzeugt man die Liste (0,1,2,3,4,5,6,7,8,9) und kann durch Mischen daraus z.B. (5,3,6,2,4,9,1,7,0,8) machen. Dies Mischen erledigt die unten implementierte Methode Shuffle.

Um die exakte Gleichverteilung aller möglichen Mischergebnisse zu erreichen, muss die Methode genau wie unten implementiert sein. Schon kleine Änderungen (z.B. ein Schleifendurchlauf mehr oder weniger) können die Gleichverteilung zerstören.

Die Shuffle-Methode basiert auf dem Algorithmus von D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, second edition. Addison-Wesley, 1981.

private static Random rand = new Random ();

public static void Shuffle<T> (IList<T> ilist)
{
    int iIndex;
    T   tTmp;
    for (int i = 1; i < ilist.Count; ++i) {
       iIndex = rand.Next (i + 1);
       tTmp = ilist [i];
       ilist [i] = ilist [iIndex];
       ilist [iIndex] = tTmp;
    }
}

// Und hier noch ein kleines Beispiel für die Verwendung:
List<int> list = new List <int> ();

for (int i = 0; i < 10; ++i) {
   list.Add (i);
}

Shuffle<int> (list);

foreach (int i in list) {
   Console.WriteLine (i);
}

Die Shuffle-Methode ließe sich natürlich leicht so abändern, dass nicht die übergebene Liste gemischt wird, sondern diese unverändert bleibt und eine Kopie der Liste gemischt und zurückgegeben wird.

Sofern (fast) alle Elemente einer Liste ohne Wiederholung ausgegeben werden sollen, ist das Snippet die einzig sinnvolle Möglichkeit, unabhängig von der Größe der Liste.

Sofern nur wenige Elemente einer Liste ohne Wiederholung ausgegeben werden sollen, kann man das Snippet auch um einen Parameter erweitern, der in der Schleife statt ilist.Count verwendet wird und es damit ermöglicht, nur die benötigte Anzahl von Schleifendurchläufen durchzuführen.

Sofern man aus einer (sehr) großen Liste im Verhältnis zu ihrer Größe nur wenige Elemente ohne Wiederholung auswählen will, kann es sinnvoller sein, wie folgt vorzugehen: In einer Schleife wählt man bei jedem Durchlauf einfach zufällig ein Element aus der gesamten Liste. Die schon gezogenen Elemente merkt man sich in einem HashSet. Wenn beim Hinzufügen feststellt wird, dass man das Element schon früher mal gezogen hatte, dann verwirft das HashSet dieses Element und man beginnt mit dem nächsten Schleifendurchlauf. Die Schleife muss natürlich solange laufen, wie HashSet.Count kleiner der Anzahl der gewünschten Elemente ist. Das HashSet merkt sich die Elemente freundlicherweise ohne mehrfache und in der Reihenfolge, wie die Elemente hinzugefügt wurden. Man kann also am Ende daraus direkt die Ergebnisliste machen (HashSet.ToList oder HashSet.ToArray).

Das im letzten Absatz Gesagte gilt um so mehr, wenn man gar keine Liste hat oder benötigt, sondern aus einen vorgegebenen (großen) Wertebereich wenige Elemente auswählen will, z.B. zehn Zufallszahlen aus dem Bereich von 0-1.000.000 ohne Wiederholung. Dann wäre es natürlich nicht sinnvoll, erste eine Liste mit einer Million (und eins) Elementen zu erzeugen, diese mit den Werten von 0-1.000.000 zu füllen, dann zu shuffeln, um dann nur die ersten 10 zu verwenden. Da ist die HashSet-Variante klar vorzuziehen.

Eine Diskussion des Snippets und anderer Verfahren findet sich in Zufallszahlen, die sich nicht wiederholen.

EDIT 15.09.2014: Siehe auch Fisher–Yates shuffle.

Schlagwörter: Random, Zufall, Zufallszahlen, Shuffle, mischen, List, Liste, IList, Swap, Dreieckstausch, Gleichverteilung, 1000 Worte

Quelle: myCSharp.de