Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Zufallszahlen, die sich nicht wiederholen
Jaden
myCSharp.de - Member



Dabei seit:
Beiträge: 21

Themenstarter:

Zufallszahlen, die sich nicht wiederholen

beantworten | zitieren | melden

Hallo,

naja, wie soll ich anfangen?...

Ich frage ein Array mit verschiedenen Werten ab.
Der Index des Arrays soll zufällig gelesen werden, soweit ok.
Naja, das Problem ist, dass der Index nur einmal abgefragt werden soll.

Also z.B. Wenn ich den Index '1' schon abgefragt wurde, soll dieser nicht
nochmal abgefragt werden.

Alle Werte dieses Array sollen zufällig aber auch nur einmal abgefragt werden.

Nun wenn ich eine Plausibiliätsprüfung einfüge, dass der wenn der auf einen
schon gewählten Index stößt weiter suchen soll, dann braucht der ne Ewigkeit
bis der alles abgefragt hat.

Bei nem kleinen Array, ist das natürlich kein Problem, aber in Größenordnung
300 bis 500 könnte dies durchaus problematisch werden. ;-)

Hatte jemand mal ein ähnliches Problem?

Also wäre sehr dankbar, wenn mir jemand helfen könnte.

Vielen Dank im Voraus!

Schöne Grüße Jaden
private Nachricht | Beiträge des Benutzers
swordfish
myCSharp.de - Member



Dabei seit:
Beiträge: 58
Herkunft: Österreich

beantworten | zitieren | melden

dann mach doch eine sorted list oder eine hashtable mit dem wert als schlüssel

somit kannst du einfach versuchen den gewählten schlüssel einzufügen und wenn der schon vorhanden ist, dann bekommst du eine exception

der zugriff über schlüssel ist denk ich mal ziemlich schnell
wer fehler findet, darf sie behalten
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

EDIT (2009): Der Original-Beitrag ist schon älter. ArrayList gehört mittlerweile in die Mottenkiste und sollte wie alle untypisierten Collections aus System.Collections nicht mehr benutzt werden. Stattdessen sollte man List<T> und alle anderen typisierten Collections aus System.Collections.Generic verwenden.

Die hier vorgeschlagene Lösung mit dem RemoveAt ist allerdings sowieso ungünstig, wie sich im weiteren Verlauf des Threads zeigt. Weiter unten werden bessere Lösungen vorgeschlagen.


Hallo Jaden,

kopiere vorab Dein Array in eine ArrayList

Erzeuge eine Zufallszahl zwischen 0 und ArrayList.Count-1. Dann kannst du den gelieferten Wert als Index verwenden, um das gewünschte Element zu ermitteln. Anschließend löscht du das Array-Element an dieser Stelle mit ArrayList.RemoveAt und generierst die nächste Zufallszahl zwischen 0 und ArrayList.Count-1, wobei Count selbst ja jetzt um eins kleiner ist.


EDIT (2012): Die folgende Variante arbeitet mit linearem Aufwand und Gleichverteilung:

kopiere vorab Array.Length in die Variable valuesLeft.

Erzeuge eine Zufallszahl zwischen 0 und valuesLeft-1. Dann kannst du den gelieferten Wert als Index verwenden, um das gewünschte Element zu ermitteln. Anschließend kopierst du das Array-Element vom Index valuesLeft an diese Stelle und generierst die nächste Zufallszahl zwischen 0 und valuesLeft-1, wobei du valuesLeft vorher um eins verringerst.

Einfacher ist es jedoch die fertige Shuffle-Methode zu verwenden, die nach einem ähnlichen Prinzip funktioniert, siehe [Snippet] Zufallszahlen, die sich nicht wiederholen. Dort wird auch noch eine andere Möglichkeit aufgezeigt, die sich besser eignet, wenn man aus einer großen Liste oder einem großen Wertebereich nur wenige Zufallszahlen (aber trotzdem ohne Wiederholung) auswählen will.


HTH

herbivore
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von herbivore am .
private Nachricht | Beiträge des Benutzers
cdr
myCSharp.de - Member



Dabei seit:
Beiträge: 1008
Herkunft: Zürich

beantworten | zitieren | melden

Noch einfacher: packe das Array in eine Sorted List mit Zufallszahlen als schlüssel. Dann gehst du die (zufällig sortierte) Liste der Reihe nach durch ...
private Nachricht | Beiträge des Benutzers
swordfish
myCSharp.de - Member



Dabei seit:
Beiträge: 58
Herkunft: Österreich

beantworten | zitieren | melden

Zitat von cdr
Noch einfacher: packe das Array in eine Sorted List mit Zufallszahlen als schlüssel. Dann gehst du die (zufällig sortierte) Liste der Reihe nach durch ...

wie ichs schon erwähnt habe*G*
wer fehler findet, darf sie behalten
private Nachricht | Beiträge des Benutzers
Pulpapex
myCSharp.de - Member



Dabei seit:
Beiträge: 962
Herkunft: Rostock

beantworten | zitieren | melden

Angelehnt an cdrs Vorschlag; in Java gibt es die Methode Collections.shuffle, die Listen durchmischt (Gegenteil von sort).

Ich denke mal eine Schleife mit Count / 2 Durchläufen, die jeweils zwei zufällig ausgewählte Listenelemente vertauscht, sollte ausreichen. Mit einem abgewandelten Quicksort oder Mergesort müsste es noch effizienter gehen.
private Nachricht | Beiträge des Benutzers
cdr
myCSharp.de - Member



Dabei seit:
Beiträge: 1008
Herkunft: Zürich

beantworten | zitieren | melden

Zitat von swordfish
wie ichs schon erwähnt habe*G*

Oh, dann habe ich wohl deine Beschreibung oben falsch verstanden, sry

Siehe auch http://www.boyet.com/Articles/SimpleShuffling.html und http://www.daimi.au.dk/~ursem/EAdocs/RKUjava/math/RKUPermutation.html
private Nachricht | Beiträge des Benutzers
swordfish
myCSharp.de - Member



Dabei seit:
Beiträge: 58
Herkunft: Österreich

beantworten | zitieren | melden

is ja kein problem :-)
wer fehler findet, darf sie behalten
private Nachricht | Beiträge des Benutzers
Jaden
myCSharp.de - Member



Dabei seit:
Beiträge: 21

Themenstarter:

beantworten | zitieren | melden

Also danke für die Antworten

Ich habs mit der Arraylist gelöst, irgendwie hab ich das mit den sorted list nicht hinbekommen.

Ich schreib grad an nen ziemlich kopfzerbrechenden Algorithmus.

Ist die Variante mit den sorted list performanter?

Schöne Grüße

Jaden
private Nachricht | Beiträge des Benutzers
Pulpapex
myCSharp.de - Member



Dabei seit:
Beiträge: 962
Herkunft: Rostock

beantworten | zitieren | melden

Ich denke nicht, dass die SortedList-Lösung performanter ist. Wahrscheinlich nimmt es sich nicht viel oder die ArrayList ist sogar schneller. Hast du dir den Algorithmus, der auf den von cdr verlinkten Seiten beschrieben wird, angeschaut? Ist ne Art Bubble-Suffle, sehr einfach.

// ArrayList rückwärts durchlaufen.
Random r = new Random();
for(int i = arrayList.Count - 1; i ≥ 1; i--) {

  // Bereich des zufälligen Indexes einschränken,
  // damit nicht unnötig viele Items doppelt getauscht werden.
  int j = r.Next(i);

  // Items vertauschen.
  object temp = arrayList[i];
  arrayList[i] = arrayList[j];
  arrayList[j] = temp;
}
private Nachricht | Beiträge des Benutzers
cdr
myCSharp.de - Member



Dabei seit:
Beiträge: 1008
Herkunft: Zürich

beantworten | zitieren | melden

Ja, die SortedList Variante wäre imo asymptotisch weniger performant -> T(n*log(n)) vs T(n) wenn ich das richtig sehe/rate
private Nachricht | Beiträge des Benutzers
swordfish
myCSharp.de - Member



Dabei seit:
Beiträge: 58
Herkunft: Österreich

beantworten | zitieren | melden

von der performance her denk auch dass sorted list langsamer ist, aber bei der arraylist können werte ja auch öfters vorkommen (ich hoffe ich irre mich jetzt nicht) -> dann müsste man das wieder expliziert abfangen -> wäre dadurch wohl wieder langsamer
wer fehler findet, darf sie behalten
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo swordfish,

wenn Du mit 'bei der arraylist' meinen Vorschlag meinst, dann kommt deshalb kein Wert doppelt vor, weil jedes verwendete Element aus der ArrayList entfernt wird.

herbivore
private Nachricht | Beiträge des Benutzers
swordfish
myCSharp.de - Member



Dabei seit:
Beiträge: 58
Herkunft: Österreich

beantworten | zitieren | melden

ok gut dann gibts das problem nicht

dann dürfte dein vorschlag wohl die beste lösung sein
wer fehler findet, darf sie behalten
private Nachricht | Beiträge des Benutzers
Pulpapex
myCSharp.de - Member



Dabei seit:
Beiträge: 962
Herkunft: Rostock

beantworten | zitieren | melden

Nee,
man darf in einer ArrayList nicht löschen. Für jedes zu löschende Element muss durchschnittlich die Hälfte aller Elemente umkopiert werden.

Bei 1.000.000 Elementen müssten zirka 125.000.000.000 Elemente kopiert werden. Der Bubbe-Shuffle-Algorithmus oben kopiert nur 2.000.000 Elemente.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Pulpapex,

ich glaube die Diskussion entgleitet uns hier etwas. Du hast natürlich recht mit dem Aufwand durch das Löschen (wobei ich nicht so weit gehen würde, dass man nicht löschen darf, denn gehen tut das ja), aber in der Originalfrage ging es um eine "Größenordnung [von] 300 bis 500".

herbivore
private Nachricht | Beiträge des Benutzers
swordfish
myCSharp.de - Member



Dabei seit:
Beiträge: 58
Herkunft: Österreich

beantworten | zitieren | melden

ja da gibt es dann sowieso nicht wirkliche performanceabstriche bei den collections

da kannste dann sowieso alles einsetzen.
wer fehler findet, darf sie behalten
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,

ich habe mich heute zufällig noch mal mit dem Thema beschäftigt. Die Variante mit dem Shuffle ist, wie wir ja schon festgestellt haben, die beste. Aber nach allem was ich gelesen habe, muss man höllisch aufpassen, damit alle möglichen Ergebnis des Mischens auch wirklich gleich wahrscheinlich sind.

Nach allem was ich weiß, ist bei der folgenden Lösung die Gleichverteilung durch genau al.Count - 1 Vertauschungen sichergestellt:


ArrayList al = new ArrayList ();
al.Add (...);

Random rand = new Random ();
int iIndex;
Object objTmp;
for (int i = 1; i < al.Count; ++i) {
   iIndex = rand.Next (i + 1);
   objTmp = al [i];
   al [i] = al [iIndex];
   al [iIndex] = objTmp;
}
Also fast wie bei Pulpapex Lösung, aber eben nur fast. Bei seiner Lösung wird - soweit ich dass sehe - in einem Array der Länge zwei z.B. nie getauscht.

herbivore

PS: Siehe auch [Snippet] Zufallszahlen, die sich nicht wiederholen

Suchhilfe: 1000 Worte
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,

interessante Überlegungen zur Gleichverteilung gibt es in Random von Namen (String) und den folgenden Beiträgen.

herbivore
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,

hier mal eine Version für .NET 2.0 unter Verwendung von Generics:


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;
    }
}
Diese 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.

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);
}
herbivore

PS: Siehe auch [Snippet] Zufallszahlen, die sich nicht wiederholen
private Nachricht | Beiträge des Benutzers
cdr
myCSharp.de - Member



Dabei seit:
Beiträge: 1008
Herkunft: Zürich

beantworten | zitieren | melden

Btw, Math.NET Iridium hat solche Methoden fest eingebaut:

MathNet.Numerics.Combinatorics:
  • int[] RandomPremutation(int n)
  • bool[] RandomCombination(int n)
  • bool[] RandomCombination(int n, int k)
  • int[] RandomCombinationWithRepetition(int n, int k)
  • int[] RandomVariation(int n, int k)
  • int[] RandomVariationWithRepetition(int n, int k)
  • void RandomShuffle<T>(IList<T> source, IList<T> target)
  • void RandomShuffle<T>(IList<T> array)
  • T[] RandomSubsetVariation<T>(IList<T> array, int numberToSelect)
  • T[] RandomSubsetVariationWithRepetition<T>(IList<T> array, int numberToSelect)
  • T[] RandomSubsetCombination<T>(IList<T> array, int numberToSelect)
  • T[] RandomSubsetCombinationWithRepetition<T>(IList<T> array, int numberToSelect)

edit: wobei ich gerade gesehen habe dass die Klasse noch etwas Verbesserungspotential haben ... (-> nächste release..)
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von cdr am .
private Nachricht | Beiträge des Benutzers
Borg
myCSharp.de - Member



Dabei seit:
Beiträge: 1548
Herkunft: Berlin, Germany

beantworten | zitieren | melden

Wobei man von "Zufallsklassen", die auf int basieren nicht zuviel erwarten sollte. Dazu ist der Zahlenbereich einfach zu klein. Näheres siehe Random von Namen (String).
private Nachricht | Beiträge des Benutzers
cdr
myCSharp.de - Member



Dabei seit:
Beiträge: 1008
Herkunft: Zürich

beantworten | zitieren | melden

Zitat von Borg
Wobei man von "Zufallsklassen", die auf int basieren nicht zuviel erwarten sollte. Dazu ist der Zahlenbereich einfach zu klein. Näheres siehe Random von Namen (String).

So nutzlos sind sie auch wieder nicht (sofern man nicht aus irgendwelchen Gründen jedes mal mit einem neuen Seed initialisiert). Nicht vergessen, dass man auch mit nur einem einzigen Seed bereits genau so viele verschiedene Zufallsfolgen generieren kann wie die Periode des Generators lang ist (einfach jeweils versetzt; eigentlich eine zweite Seed-Dimension).

Wenn man bedenkt dass man z.B. mit einem mwc-rng Periodenlängen von 2^131102 erreichen kann ist das einiges, und reicht problemlos um pro Seed alle Permutationen einer Folge von 10000 Elementen ( =2^118458 ) theoretisch direkt abbilden zu können. Iridium bietet beispielsweise einen RNG mit Periode 2^19937, das reicht immerhin um pro Seed alle Permutationen einer Folge von 2000 Elementen ( =2^19052 ) theoretisch direkt abbilden zu können. Nicht dass es notwendig wäre die Permutationen direkt abbilden zu können...

edit: automatische smilies entfernt

edit2: -> Entscheidender als die Seedlänge ist also die Periodenlänge. Kennt zufällig jemand die Periodenlänge von System.Random und System.Security.Cryptography.RNGCryptoServiceProvider?
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von cdr am .
private Nachricht | Beiträge des Benutzers
BillTuer
myCSharp.de - Member



Dabei seit:
Beiträge: 325
Herkunft: Gießen

beantworten | zitieren | melden

Gibt es auch eine Möglichkeit, Werte aus einer Liste zufällig zu bestimmen (ohne Wiederholung), ohne dabei ein Element zu entfernen und dann 0 - Count-1 als Range zu wählen?
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von BillTuer am .
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo BillTuer,

wenn du Zufallszahlen haben willst, die sich nicht wiederholen, wurden ja verschiedene Möglichkeiten genannt, wie das ohne Remove geht.

Wenn es das nicht trifft, dann beschreibe bitte genauer, was du eigentlich erreichen willst.

herbivore
private Nachricht | Beiträge des Benutzers
BillTuer
myCSharp.de - Member



Dabei seit:
Beiträge: 325
Herkunft: Gießen

beantworten | zitieren | melden

Ich denke, ich habe eine Lösung gefunden. Ich vergleiche mein Ergebnis einfach mit dem davor, wenn es gleich ist, "würfel" ich neu...


Random random = new Random();
Int32 indexRandom = random.Next(0, _listLala.Count);
while (_listLala[indexRandom] == lala)
{
    indexRandom = random.Next(0, _listLala.Count);
}
lala = _listLala[indexRandom];
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo BillTuer,

damit ist aber nur sichergestellt, dass zwei direkt aufeinanderfolgende Zahlen nicht gleich sind.

Außerdem wird nicht geschaut, ob die Zufallszahl gleich ist oder nicht, sondern die aus der Liste gewählte Zahl. Enthält die Liste an allen Stellen die gleiche Zahl, ist deine while-Schleife eine Endlosschleife.

Aber ich verstehe sowieso nicht, warum du die Frage überhaupt gestellt hast, denn der Thread ist ja voll mit Lösungen für dein Problem.

herbivore
private Nachricht | Beiträge des Benutzers
BillTuer
myCSharp.de - Member



Dabei seit:
Beiträge: 325
Herkunft: Gießen

beantworten | zitieren | melden

Ach, habe total umständlich und dumm gedacht.
Ist alles gut. Sorry und danke
private Nachricht | Beiträge des Benutzers
kleines_eichhoernchen
myCSharp.de - Member

Avatar #avatar-2079.jpg


Dabei seit:
Beiträge: 4055
Herkunft: Ursprünglich Vogtland, jetzt Much

beantworten | zitieren | melden

Gehört zwar nicht ganz so zum Thema, aber falls man (neben der aktuellen Zeit) mal einen gescheiten Seed braucht:


Random rnd = new Random(Guid.CreateNew().GetHashCode());
Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...
private Nachricht | Beiträge des Benutzers

Moderationshinweis von herbivore (15.09.2014 - 08:28:31):

Siehe auch Highspeed Algorithmus zur Namenserstellung aus 2 Listen für eine detaillierte Diskussion verschiedener Ansätze, inkl. eines hier noch nicht besprochenen Ansatzes mit einer Laufzeit von O(n) und einem Speicherbedarf von O(1). In Highspeed Algorithmus zur Namenserstellung aus 2 Listen gib es eine effiziente Implementierung dieses Verfahrens.