Laden...

Zufallszahlen, die sich nicht wiederholen

Erstellt von Jaden vor 19 Jahren Letzter Beitrag vor 15 Jahren 40.485 Views
J
Jaden Themenstarter:in
21 Beiträge seit 2004
vor 19 Jahren
Zufallszahlen, die sich nicht wiederholen

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

S
58 Beiträge seit 2004
vor 19 Jahren

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

49.485 Beiträge seit 2005
vor 19 Jahren

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

C
980 Beiträge seit 2003
vor 19 Jahren

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 ...

S
58 Beiträge seit 2004
vor 19 Jahren

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 habeG

wer fehler findet, darf sie behalten

P
939 Beiträge seit 2003
vor 19 Jahren

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.

C
980 Beiträge seit 2003
vor 19 Jahren

wie ichs schon erwähnt habeG

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

S
58 Beiträge seit 2004
vor 19 Jahren

is ja kein problem 🙂

wer fehler findet, darf sie behalten

J
Jaden Themenstarter:in
21 Beiträge seit 2004
vor 19 Jahren

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

P
939 Beiträge seit 2003
vor 19 Jahren

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;
}
C
980 Beiträge seit 2003
vor 19 Jahren

Ja, die SortedList Variante wäre imo asymptotisch weniger performant -> T(n*log(n)) vs T(n) wenn ich das richtig sehe/rate 😉

S
58 Beiträge seit 2004
vor 19 Jahren

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

49.485 Beiträge seit 2005
vor 19 Jahren

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

S
58 Beiträge seit 2004
vor 19 Jahren

ok gut dann gibts das problem nicht

dann dürfte dein vorschlag wohl die beste lösung sein

wer fehler findet, darf sie behalten

P
939 Beiträge seit 2003
vor 19 Jahren

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.

49.485 Beiträge seit 2005
vor 19 Jahren

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

S
58 Beiträge seit 2004
vor 19 Jahren

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

da kannste dann sowieso alles einsetzen.

wer fehler findet, darf sie behalten

49.485 Beiträge seit 2005
vor 18 Jahren

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

49.485 Beiträge seit 2005
vor 17 Jahren

Hallo zusammen,

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

herbivore

49.485 Beiträge seit 2005
vor 17 Jahren

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

C
980 Beiträge seit 2003
vor 17 Jahren

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..)

B
1.529 Beiträge seit 2006
vor 17 Jahren

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).

C
980 Beiträge seit 2003
vor 17 Jahren

Wobei man von "Zufallsklassen", die auf int basieren nicht zuviel erwarten sollte. Dazu ist der Zahlenbereich einfach zu klein. Näheres siehe
>
.

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 2131102 erreichen kann ist das einiges, und reicht problemlos um pro Seed alle Permutationen einer Folge von 10000 Elementen ( =2118458 ) theoretisch direkt abbilden zu können. Iridium bietet beispielsweise einen RNG mit Periode 219937, das reicht immerhin um pro Seed alle Permutationen einer Folge von 2000 Elementen ( =219052 ) 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?

B
325 Beiträge seit 2005
vor 16 Jahren

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?

49.485 Beiträge seit 2005
vor 16 Jahren

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

B
325 Beiträge seit 2005
vor 16 Jahren

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

49.485 Beiträge seit 2005
vor 16 Jahren

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

B
325 Beiträge seit 2005
vor 16 Jahren

Ach, habe total umständlich und dumm gedacht.
Ist alles gut. Sorry und danke 🙂

3.971 Beiträge seit 2006
vor 15 Jahren

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...

Hinweis von herbivore vor 9 Jahren

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.