myCSharp.de - DIE C# und .NET Community
Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 
 | Suche | FAQ

» Hauptmenü
myCSharp.de
» Startseite
» Forum
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Suche
» Regeln
» Wie poste ich richtig?
» Forum-FAQ

Mitglieder
» Liste / Suche
» Wer ist wo online?

Ressourcen
» openbook: Visual C#
» openbook: OO
» Microsoft Docs

Team
» Kontakt
» Übersicht
» Wir über uns

» myCSharp.de Diskussionsforum
Du befindest Dich hier: Community-Index » Diskussionsforum » Gemeinschaft » .NET-Komponenten und C#-Snippets » [Snippet] Zufallszahlen, die sich nicht wiederholen
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | Thema zu Favoriten hinzufügen

Antwort erstellen
Zum Ende der Seite springen  

[Snippet] Zufallszahlen, die sich nicht wiederholen

 
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
herbivore
myCSharp.de-Poweruser/ Experte

avatar-2627.gif


Dabei seit: 11.01.2005
Beiträge: 49.478
Entwicklungsumgebung: csc/nmake (nothing is faster)
Herkunft: Berlin


herbivore ist offline

[Snippet] Zufallszahlen, die sich nicht wiederholen

Beitrag: beantworten | zitieren | editieren | melden/löschen       | Top

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.

C#-Code:
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
13.05.2007 10:32 E-Mail | Beiträge des Benutzers | zu Buddylist hinzufügen
Baumstruktur | Brettstruktur       | Top 
myCSharp.de | Forum Der Startbeitrag ist älter als 13 Jahre.
Der letzte Beitrag ist älter als 13 Jahre.
Antwort erstellen


© Copyright 2003-2020 myCSharp.de-Team | Impressum | Datenschutz | Alle Rechte vorbehalten. | Dieses Portal verwendet zum korrekten Betrieb Cookies. 11.08.2020 03:40