Wählen Sie N zufällige Elemente aus einer Liste <T> in C # aus
158
Ich brauche einen schnellen Algorithmus, um 5 zufällige Elemente aus einer generischen Liste auszuwählen. Zum Beispiel möchte ich 5 zufällige Elemente von a erhalten List<string>.
Meinen Sie mit "zufällig" "Inklusiv" oder "Exklusiv"? IOW, kann dasselbe Element mehrmals ausgewählt werden? (wirklich zufällig) Oder sollte ein einmal ausgewähltes Element nicht mehr aus dem verfügbaren Pool ausgewählt werden können?
Durchlaufen und für jedes Element die Wahrscheinlichkeit der Auswahl festlegen = (benötigte Anzahl) / (verbleibende Anzahl)
Wenn Sie also 40 Artikel hätten, hätte der erste eine Chance von 5/40, ausgewählt zu werden. Wenn dies der Fall ist, hat der nächste eine Chance von 4/39, andernfalls eine Chance von 5/39. Wenn Sie am Ende angekommen sind, haben Sie Ihre 5 Gegenstände, und oft haben Sie alle vorher.
Ich finde das auf subtile Weise falsch. Es scheint, dass das hintere Ende der Liste häufiger ausgewählt wird als das vordere Ende, da das hintere Ende viel größere Wahrscheinlichkeiten aufweist. Wenn beispielsweise die ersten 35 Nummern nicht ausgewählt werden, müssen die letzten 5 Nummern ausgewählt werden. Die erste Zahl wird immer nur eine 5/40-Chance sehen, aber die letzte Zahl wird 1/1 häufiger als 5/40 Mal sehen. Sie müssen die Liste zuerst randomisieren, bevor Sie diesen Algorithmus implementieren.
Ankur Goel
23
ok, ich habe diesen Algorithmus 10 Millionen Mal auf einer Liste von 40 Elementen ausgeführt, jedes mit einem 5/40 (.125) Versuch, ausgewählt zu werden, und diese Simulation dann mehrmals ausgeführt. Es stellt sich heraus, dass dies nicht gleichmäßig verteilt ist. Die Elemente 16 bis 22 werden untergewählt (16 = .123, 17 = .124), während das Element 34 übergewählt wird (34 = .129). Die Elemente 39 und 40 werden ebenfalls untergewählt, jedoch nicht so stark (39 = .1247, 40 = .1246)
Ankur Goel
21
@Ankur: Ich glaube nicht, dass das statistisch signifikant ist. Ich glaube, es gibt einen induktiven Beweis dafür, dass dies eine gleichmäßige Verteilung ermöglicht.
rekursiv
9
Ich habe den gleichen Versuch 100 Millionen Mal wiederholt, und in meinem Versuch wurde der am wenigsten ausgewählte Gegenstand weniger als 0,106% seltener als der am häufigsten gewählte Gegenstand ausgewählt.
rekursiv
5
@recursive: Der Beweis ist fast trivial. Wir wissen, wie man K Elemente aus K für jedes K auswählt und wie man 0 Elemente aus N für jedes N auswählt. Angenommen, wir kennen eine Methode, um K oder K-1 Elemente aus N-1> = K einheitlich auszuwählen; dann können wir K Elemente aus N auswählen, indem wir das erste Element mit der Wahrscheinlichkeit K / N auswählen und dann mit der bekannten Methode die noch benötigten K- oder K-1-Elemente aus den verbleibenden N-1 auswählen.
+1 Wenn jedoch zwei Elemente die gleiche Nummer von rnd.Next () oder ähnlichem erhalten, wird das erste ausgewählt und das zweite möglicherweise nicht (wenn keine weiteren Elemente benötigt werden). Es ist jedoch je nach Verwendung richtig zufällig genug.
Lasse Espeholt
7
Ich denke, die Reihenfolge nach ist O (n log (n)), daher würde ich diese Lösung wählen, wenn die Einfachheit des Codes das Hauptanliegen ist (dh bei kleinen Listen).
Guido
2
Aber zählt und sortiert das nicht die ganze Liste? Es sei denn, mit "schnell" meinte OP "einfach", nicht "performant" ...
drzaus
2
Dies funktioniert nur, wenn OrderBy () den Schlüsselwähler für jedes Element nur einmal aufruft. Wenn es aufgerufen wird, wann immer es einen Vergleich zwischen zwei Elementen durchführen möchte, erhält es jedes Mal einen anderen Wert zurück, was die Sortierung vermasselt. Die [Dokumentation] ( msdn.microsoft.com/en-us/library/vstudio/… ) sagt nicht, was sie tut.
Oliver Bock
2
Achten Sie darauf, ob YourListes viele Artikel gibt, aber Sie möchten nur einige auswählen. In diesem Fall ist dies keine effiziente Methode.
Dies ist tatsächlich ein schwierigeres Problem, als es sich anhört, hauptsächlich weil viele mathematisch korrekte Lösungen es Ihnen nicht ermöglichen, alle Möglichkeiten zu nutzen (mehr dazu weiter unten).
Hier sind zunächst einige einfach zu implementierende, korrekte, wenn Sie einen wirklich zufälligen Zahlengenerator haben:
(0) Kyles Antwort ist O (n).
(1) Generieren Sie eine Liste von n Paaren [(0, Rand), (1, Rand), (2, Rand), ...], sortieren Sie sie nach der zweiten Koordinate und verwenden Sie das erste k (für Sie k = 5) Indizes, um Ihre zufällige Teilmenge zu erhalten. Ich denke, das ist einfach zu implementieren, obwohl es O (n log n) Zeit ist.
(2) Initiiere eine leere Liste s = [], die zu den Indizes von k zufälligen Elementen wird. Wählen Sie zufällig eine Zahl r in {0, 1, 2, ..., n-1}, r = rand% n, und addieren Sie diese zu s. Als nächstes nimm r = rand% (n-1) und stecke in s; Fügen Sie zu r die # Elemente weniger als in s hinzu, um Kollisionen zu vermeiden. Nehmen Sie als nächstes r = rand% (n-2) und machen Sie dasselbe usw., bis Sie k verschiedene Elemente in s haben. Dies hat die Worst-Case-Laufzeit O (k ^ 2). Für k << n kann dies also schneller sein. Wenn Sie s sortiert halten und verfolgen, welche zusammenhängenden Intervalle es hat, können Sie es in O (k log k) implementieren, aber es ist mehr Arbeit.
@ Kyle - du hast recht, beim zweiten Gedanken stimme ich deiner Antwort zu. Ich habe es zuerst hastig gelesen und fälschlicherweise gedacht, Sie würden nacheinander jedes Element mit fester Wahrscheinlichkeit k / n auswählen, was falsch gewesen wäre - aber Ihr adaptiver Ansatz erscheint mir richtig. Das tut mir leid.
Ok, und jetzt zum Kicker: asymptotisch (für festes k, n Wachstum) gibt es n ^ k / k! Auswahl der k-Element-Teilmenge aus n Elementen [dies ist eine Annäherung an (n wähle k)]. Wenn n groß und k nicht sehr klein ist, sind diese Zahlen riesig. Die beste Zykluslänge, auf die Sie in einem Standard-32-Bit-Zufallszahlengenerator hoffen können, ist 2 ^ 32 = 256 ^ 4. Wenn wir also eine Liste mit 1000 Elementen haben und zufällig 5 auswählen möchten, kann ein Standard-Zufallszahlengenerator auf keinen Fall alle Möglichkeiten nutzen. Solange Sie jedoch mit einer Auswahl einverstanden sind, die für kleinere Mengen gut funktioniert und immer zufällig "aussieht", sollten diese Algorithmen in Ordnung sein.
Nachtrag : Nachdem ich dies geschrieben hatte, wurde mir klar, dass es schwierig ist, Idee (2) richtig umzusetzen, deshalb wollte ich diese Antwort klarstellen. Um die O (k log k) -Zeit zu erhalten, benötigen Sie eine Array-ähnliche Struktur, die O (log m) -Suchen und Einfügungen unterstützt - ein ausgeglichener Binärbaum kann dies tun. Verwenden Sie eine solche Struktur, um ein Array namens s aufzubauen. Hier ist ein Pseudopython:
# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):for i in range(k):
r =UniformRandom(0, n-i)# May be 0, must be < n-i
q = s.FirstIndexSuchThat( s[q]- q > r )# This is the search.
s.InsertInOrder(q ? r + q : r + len(s))# Inserts right before q.return s
Ich schlage vor, einige Beispielfälle durchzugehen, um zu sehen, wie dies die obige englische Erklärung effizient umsetzt.
Für (1) können Sie eine Liste schneller mischen als für das Sortieren. Für (2) werden Sie Ihre Verteilung mit%
jk beeinflussen.
In Anbetracht der Einwand Sie über die Zykluslänge eines RNG erhöht, ist es eine Möglichkeit , wir können einen Algorithmus konstruieren , das alle Sätze mit gleicher Wahrscheinlichkeit wählen werden?
Jonah
Für (1) können Sie zur Verbesserung des O (n log (n)) die Auswahlsortierung verwenden, um die k kleinsten Elemente zu finden. Das läuft in O (n * k).
Jared
@ Jonah: Ich denke schon. Nehmen wir an, wir können mehrere unabhängige Zufallszahlengeneratoren kombinieren, um einen größeren zu erstellen ( crypto.stackexchange.com/a/27431 ). Dann brauchen Sie nur einen Bereich, der groß genug ist, um mit der Größe der betreffenden Liste fertig zu werden.
Jared
16
Ich denke, die ausgewählte Antwort ist richtig und ziemlich süß. Ich habe es allerdings anders implementiert, da ich das Ergebnis auch in zufälliger Reihenfolge haben wollte.
staticIEnumerable<SomeType>PickSomeInRandomOrder<SomeType>(IEnumerable<SomeType> someTypes,int maxCount){Random random =newRandom(DateTime.Now.Millisecond);Dictionary<double,SomeType> randomSortTable =newDictionary<double,SomeType>();foreach(SomeType someType in someTypes)
randomSortTable[random.NextDouble()]= someType;return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);}
Haben Sie einen Grund, kein neues Random () zu verwenden, das auf Environment.TickCount vs. DateTime.Now.Millisecond basiert?
Lasse Espeholt
Nein, ich wusste nur nicht, dass es einen Standard gibt.
Frank Schwieterman
Eine Verbesserung der randomSortTable: randomSortTable = someTypes.ToDictionary (x => random.NextDouble (), y => y); Speichert die foreach-Schleife.
Keltex
2
OK, ein Jahr zu spät, aber ... Entspricht dies nicht der eher kürzeren Antwort von @ ersin, und scheitert es nicht, wenn Sie eine wiederholte Zufallszahl erhalten (wobei Ersins eine Tendenz zum ersten Punkt eines wiederholten Paares hat)?
Andiih
12
Ich bin gerade auf dieses Problem gestoßen, und einige weitere Google-Suchanfragen haben mich zu dem Problem gebracht, eine Liste zufällig zu mischen: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
Um Ihre Liste (zufällig) vollständig zufällig zu mischen, gehen Sie folgendermaßen vor:
So mischen Sie ein Array a von n Elementen (Indizes 0..n-1):
for i from n −1 downto 1do
j ← random integer with 0≤ j ≤ i
exchange a[j] and a[i]
Wenn Sie nur die ersten 5 Elemente benötigen, müssen Sie i nicht von n-1 bis 1 ausführen, sondern nur n-5 (dh: n-5).
Nehmen wir an, Sie brauchen k Gegenstände,
Dies wird:
for(i = n −1; i >= n-k; i--){
j = random integer with 0≤ j ≤ i
exchange a[j] and a[i]}
Jedes ausgewählte Element wird gegen Ende des Arrays ausgetauscht, sodass die ausgewählten k Elemente die letzten k Elemente des Arrays sind.
Dies dauert Zeit O (k), wobei k die Anzahl der zufällig ausgewählten Elemente ist, die Sie benötigen.
Wenn Sie Ihre ursprüngliche Liste nicht ändern möchten, können Sie alle Ihre Swaps in eine temporäre Liste eintragen, diese Liste umkehren und erneut anwenden. Auf diese Weise können Sie den umgekehrten Satz von Swaps ausführen und Ihre ursprüngliche Liste ohne Änderung zurückgeben die O (k) Laufzeit.
Wenn Sie für den echten Stickler (n == k) sind, sollten Sie bei 1 und nicht bei nk anhalten, da die zufällig ausgewählte Ganzzahl immer 0 ist.
Erhalten Sie nur genug Elemente in der Liste, aber nicht zufällig.
Culithay
2
Diese Implementierung ist fehlerhaft, weil die Verwendung von varin neededund availablebeide Ganzzahlen sind, was needed/availableimmer 0 ergibt .
Niko
1
Dies scheint eine Implementierung der akzeptierten Antwort zu sein.
DCShannon
6
Die Auswahl von N zufälligen Elementen aus einer Gruppe sollte nichts mit der Bestellung zu tun haben ! Bei Zufälligkeit geht es um Unvorhersehbarkeit und nicht darum, Positionen in einer Gruppe zu mischen. Alle Antworten, die sich mit einer Art Bestellung befassen, sind weniger effizient als diejenigen, die dies nicht tun. Da Effizienz hier der Schlüssel ist, werde ich etwas veröffentlichen, das die Reihenfolge der Artikel nicht zu sehr ändert.
1) Wenn Sie echte Zufallswerte benötigen , was bedeutet, dass es keine Einschränkung gibt, aus welchen Elementen Sie auswählen können (dh sobald das ausgewählte Element erneut ausgewählt werden kann):
Wenn Sie das Ausnahmeflag deaktivieren, können Sie beliebig oft zufällige Elemente auswählen.
Wenn Sie {1, 2, 3, 4} haben, kann es {1, 4, 4}, {1, 4, 3} usw. für 3 Elemente oder sogar {1, 4, 3, 2, 4} für geben 5 Artikel!
Dies sollte ziemlich schnell gehen, da es nichts zu überprüfen gibt.
2) Wenn Sie einzelne Mitglieder aus der Gruppe ohne Wiederholung benötigen , würde ich mich auf ein Wörterbuch verlassen (wie viele bereits betont haben).
Der Code ist hier etwas länger als bei anderen Wörterbuchansätzen, da ich ihn nicht nur hinzufüge, sondern auch aus der Liste entferne, also sind es irgendwie zwei Schleifen. Sie können hier sehen, dass ich überhaupt nichts nachbestellt habe, wenn es countgleich wird source.Count. Das liegt daran, dass ich glaube, dass Zufälligkeit im gesamten zurückgegebenen Set enthalten sein sollte . Ich meine , wenn Sie wollen 5 zufällige Elemente aus 1, 2, 3, 4, 5, sollte es keine Rolle , ob seine 1, 3, 4, 2, 5oder 1, 2, 3, 4, 5, aber wenn Sie benötigen 4 Elemente aus dem gleichen Satz, dann sollte es unvorhersehbar Ausbeute in 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4usw. Zweitens , wenn die Anzahl der zufälligen Elemente sein zurückgegeben wird mehr als die Hälfte der ursprünglichen Gruppe, dann ist es einfacher zu entfernensource.Count - countElemente aus der Gruppe als Hinzufügen von countElementen. Aus Leistungsgründen habe ich sourcestattdessen verwendet sourceDict, um dann einen zufälligen Index in der Methode remove zu erhalten.
Wenn Sie also {1, 2, 3, 4} haben, kann dies für 3 Elemente zu {1, 2, 3}, {3, 4, 1} usw. führen.
3) Wenn Sie wirklich unterschiedliche Zufallswerte aus Ihrer Gruppe benötigen, indem Sie die Duplikate in der ursprünglichen Gruppe berücksichtigen, können Sie den gleichen Ansatz wie oben verwenden, aber a HashSetist leichter als ein Wörterbuch.
Die randomsVariable wird erstellt HashSet, um zu vermeiden, dass in den seltensten Fällen Duplikate hinzugefügt werden, in denen Random.Nextder gleiche Wert erzielt werden kann, insbesondere wenn die Eingabeliste klein ist.
Also {1, 2, 2, 4} => 3 zufällige Elemente => {1, 2, 4} und niemals {1, 2, 2}
{1, 2, 2, 4} => 4 zufällige Elemente => Ausnahme !! oder {1, 2, 4} je nach gesetztem Flag.
Einige der Erweiterungsmethoden, die ich verwendet habe:
Wenn es um Leistung geht, bei der Zehntausende von Elementen in der Liste 10000 Mal wiederholt werden müssen, möchten Sie vielleicht eine schnellere Zufallsklasse als System.Random, aber ich denke nicht, dass dies eine große Sache ist, wenn man bedenkt, dass letztere höchstwahrscheinlich niemals eine ist Engpass, es ist ziemlich schnell genug ..
Bearbeiten: Wenn Sie auch die Reihenfolge der zurückgegebenen Artikel neu ordnen müssen, gibt es nichts, was Dhakims Fisher-Yates-Ansatz übertreffen könnte - kurz, süß und einfach.
Ich habe über einen Kommentar von @JohnShedletsky zu der akzeptierten Antwort bezüglich (Paraphrase) nachgedacht :
Sie sollten dies in O (subset.Length) und nicht in O (originalList.Length) tun können.
Grundsätzlich sollten Sie in der Lage sein, subsetzufällige Indizes zu generieren und diese dann aus der ursprünglichen Liste zu entfernen.
Die Methode
publicstaticclassEnumerableExtensions{publicstaticRandom randomizer =newRandom();// you'd ideally be able to replace this with whatever makes you comfortablepublicstaticIEnumerable<T>GetRandom<T>(thisIEnumerable<T>list,int numItems){return(listas T[]??list.ToArray()).GetRandom(numItems);// because ReSharper whined about duplicate enumeration.../*
items.Add(list.ElementAt(randomizer.Next(list.Count()))) ) numItems--;
*/}// just because the parentheses were getting confusingpublicstaticIEnumerable<T>GetRandom<T>(this T[]list,int numItems){var items =newHashSet<T>();// don't want to add the same item twice; otherwise use a listwhile(numItems >0)// if we successfully added it, move onif( items.Add(list[randomizer.Next(list.Length)])) numItems--;return items;}// and because it's really fun; note -- you may get repetitionpublicstaticIEnumerable<T>PluckRandomly<T>(thisIEnumerable<T>list){while(true)yieldreturnlist.ElementAt(randomizer.Next(list.Count()));}}
Wenn Sie noch effizienter sein möchten, würden Sie wahrscheinlich einen HashSetder Indizes verwenden , nicht die tatsächlichen Listenelemente (falls Sie komplexe Typen oder teure Vergleiche haben).
Der Unit Test
Und um sicherzustellen, dass wir keine Kollisionen usw. haben.
[TestClass]publicclassRandomizingTests:UnitTestBase{[TestMethod]publicvoidGetRandomFromList(){this.testGetRandomFromList((list, num)=>list.GetRandom(num));}[TestMethod]publicvoidPluckRandomly(){this.testGetRandomFromList((list, num)=>list.PluckRandomly().Take(num), requireDistinct:false);}privatevoid testGetRandomFromList(Func<IEnumerable<int>,int,IEnumerable<int>> methodToGetRandomItems,int numToTake =10,int repetitions =100000,bool requireDistinct =true){var items =Enumerable.Range(0,100);IEnumerable<int> randomItems =null;while( repetitions-->0){
randomItems = methodToGetRandomItems(items, numToTake);Assert.AreEqual(numToTake, randomItems.Count(),"Did not get expected number of items {0}; failed at {1} repetition--", numToTake, repetitions);if(requireDistinct)Assert.AreEqual(numToTake, randomItems.Distinct().Count(),"Collisions (non-unique values) found, failed at {0} repetition--", repetitions);Assert.IsTrue(randomItems.All(o => items.Contains(o)),"Some unknown values found; failed at {0} repetition--", repetitions);}}}
Gute Idee mit Problemen. (1) Wenn Ihre größere Liste sehr groß ist (z. B. aus einer Datenbank gelesen), erkennen Sie die gesamte Liste, was den Speicher überschreiten kann. (2) Wenn K in der Nähe von N liegt, werden Sie viel nach einem nicht beanspruchten Index in Ihrer Schleife suchen, was dazu führt, dass der Code eine unvorhersehbare Zeit benötigt. Diese Probleme sind lösbar.
Paul Chernoch
1
Meine Lösung für das Problem des Dreschens lautet: Wenn K <N / 2, mach es wie du willst. Wenn K> = N / 2, wählen Sie die Indizes, die NICHT beibehalten werden sollen, anstelle der Indizes, die beibehalten werden sollen. Es gibt immer noch einige Prügel, aber viel weniger.
Paul Chernoch
Beachten Sie auch, dass dies die Reihenfolge der aufgezählten Elemente ändert, was in einigen Situationen akzeptabel sein kann, in anderen jedoch nicht.
Paul Chernoch
Im Durchschnitt scheint der Algorithmus für K = N / 2 (der schlechteste Fall für Pauls vorgeschlagene Verbesserung) ~ 0,693 * N Iterationen zu dauern. Führen Sie jetzt einen Geschwindigkeitsvergleich durch. Ist das besser als die akzeptierte Antwort? Für welche Stichprobengrößen?
mbomb007
6
Ich habe mehrere der oben genannten Antworten kombiniert, um eine von Lazily evaluierte Erweiterungsmethode zu erstellen. Meine Tests haben gezeigt, dass Kyles Ansatz (Reihenfolge (N)) um ein Vielfaches langsamer ist als die Verwendung eines Satzes durch drzaus, um die zu wählenden Zufallsindizes vorzuschlagen (Reihenfolge (K)). Ersteres führt viel mehr Aufrufe an den Zufallszahlengenerator durch und iteriert mehrmals über die Elemente.
Die Ziele meiner Implementierung waren:
1) Verwirklichen Sie nicht die vollständige Liste, wenn Sie eine IEnumerable angeben, die keine IList ist. Wenn ich eine Folge von zig Elementen erhalte, möchte ich nicht über genügend Speicher verfügen. Verwenden Sie Kyles Ansatz für eine Online-Lösung.
2) Wenn ich feststellen kann, dass es sich um eine IList handelt, verwenden Sie den Ansatz von drzaus mit einer Wendung. Wenn K mehr als die Hälfte von N ist, riskiere ich einen Schlag, da ich immer wieder viele zufällige Indizes auswähle und sie überspringen muss. Daher erstelle ich eine Liste der Indizes, die NICHT aufbewahrt werden sollen.
3) Ich garantiere, dass die Artikel in der Reihenfolge zurückgegeben werden, in der sie angetroffen wurden. Kyles Algorithmus erforderte keine Änderung. Der Algorithmus von drzaus erforderte, dass ich keine Elemente in der Reihenfolge aussende, in der die Zufallsindizes ausgewählt wurden. Ich sammle alle Indizes in einem SortedSet und gebe dann Elemente in sortierter Indexreihenfolge aus.
4) Wenn K im Vergleich zu N groß ist und ich den Sinn der Menge invertiere, zähle ich alle Elemente auf und teste, ob der Index nicht in der Menge ist. Dies bedeutet, dass ich die Laufzeit der Bestellung (K) verliere, aber da K in diesen Fällen nahe bei N liegt, verliere ich nicht viel.
Hier ist der Code:
/// <summary>/// Takes k elements from the next n elements at random, preserving their order./// /// If there are fewer than n elements in items, this may return fewer than k elements./// </summary>/// <typeparam name="TElem">Type of element in the items collection.</typeparam>/// <param name="items">Items to be randomly selected.</param>/// <param name="k">Number of items to pick.</param>/// <param name="n">Total number of items to choose from./// If the items collection contains more than this number, the extra members will be skipped./// If the items collection contains fewer than this number, it is possible that fewer than k items will be returned.</param>/// <returns>Enumerable over the retained items./// /// See http://stackoverflow.com/questions/48087/select-a-random-n-elements-from-listt-in-c-sharp for the commentary./// </returns>publicstaticIEnumerable<TElem>TakeRandom<TElem>(thisIEnumerable<TElem> items,int k,int n){var r =newFastRandom();var itemsList = items asIList<TElem>;if(k >= n ||(itemsList !=null&& k >= itemsList.Count))foreach(var item in items)yieldreturn item;else{// If we have a list, we can infer more information and choose a better algorithm.// When using an IList, this is about 7 times faster (on one benchmark)!if(itemsList !=null&& k < n/2){// Since we have a List, we can use an algorithm suitable for Lists.// If there are fewer than n elements, reduce n.
n =Math.Min(n, itemsList.Count);// This algorithm picks K index-values randomly and directly chooses those items to be selected.// If k is more than half of n, then we will spend a fair amount of time thrashing, picking// indices that we have already picked and having to try again. var invertSet = k >= n/2;var positions = invertSet ?(ISet<int>)newHashSet<int>():(ISet<int>)newSortedSet<int>();var numbersNeeded = invertSet ? n - k : k;while(numbersNeeded >0)if(positions.Add(r.Next(0, n))) numbersNeeded--;if(invertSet){// positions contains all the indices of elements to Skip.for(var itemIndex =0; itemIndex < n; itemIndex++){if(!positions.Contains(itemIndex))yieldreturn itemsList[itemIndex];}}else{// positions contains all the indices of elements to Take.foreach(var itemIndex in positions)yieldreturn itemsList[itemIndex];}}else{// Since we do not have a list, we will use an online algorithm.// This permits is to skip the rest as soon as we have enough items.var found =0;var scanned =0;foreach(var item in items){var rand = r.Next(0,n-scanned);if(rand < k - found){yieldreturn item;
found++;}
scanned++;if(found >= k || scanned >= n)break;}}}}
Ich verwende einen speziellen Zufallszahlengenerator, aber Sie können einfach C # 's Random verwenden, wenn Sie möchten. ( FastRandom wurde von Colin Green geschrieben und ist Teil von SharpNEAT. Es hat eine Periode von 2 ^ 128-1, was besser ist als bei vielen RNGs.)
Hier sind die Unit-Tests:
[TestClass]publicclassTakeRandomTests{/// <summary>/// Ensure that when randomly choosing items from an array, all items are chosen with roughly equal probability./// </summary>[TestMethod]publicvoidTakeRandom_Array_Uniformity(){constint numTrials =2000000;constint expectedCount = numTrials/20;var timesChosen =newint[100];var century =newint[100];for(var i =0; i < century.Length; i++)
century[i]= i;for(var trial =0; trial < numTrials; trial++){foreach(var i in century.TakeRandom(5,100))
timesChosen[i]++;}var avg = timesChosen.Average();var max = timesChosen.Max();var min = timesChosen.Min();var allowedDifference = expectedCount/100;AssertBetween(avg, expectedCount -2, expectedCount +2,"Average");//AssertBetween(min, expectedCount - allowedDifference, expectedCount, "Min");//AssertBetween(max, expectedCount, expectedCount + allowedDifference, "Max");var countInRange = timesChosen.Count(i => i >= expectedCount - allowedDifference && i <= expectedCount + allowedDifference);Assert.IsTrue(countInRange >=90,String.Format("Not enough were in range: {0}", countInRange));}/// <summary>/// Ensure that when randomly choosing items from an IEnumerable that is not an IList, /// all items are chosen with roughly equal probability./// </summary>[TestMethod]publicvoidTakeRandom_IEnumerable_Uniformity(){constint numTrials =2000000;constint expectedCount = numTrials /20;var timesChosen =newint[100];for(var trial =0; trial < numTrials; trial++){foreach(var i inRange(0,100).TakeRandom(5,100))
timesChosen[i]++;}var avg = timesChosen.Average();var max = timesChosen.Max();var min = timesChosen.Min();var allowedDifference = expectedCount /100;var countInRange =
timesChosen.Count(i => i >= expectedCount - allowedDifference && i <= expectedCount + allowedDifference);Assert.IsTrue(countInRange >=90,String.Format("Not enough were in range: {0}", countInRange));}privateIEnumerable<int>Range(int low,int count){for(var i = low; i < low + count; i++)yieldreturn i;}privatestaticvoidAssertBetween(int x,int low,int high,String message){Assert.IsTrue(x > low,String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));Assert.IsTrue(x < high,String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));}privatestaticvoidAssertBetween(double x,double low,double high,String message){Assert.IsTrue(x > low,String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));Assert.IsTrue(x < high,String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));}}
Gibt es keinen Fehler im Test? Sie haben if (itemsList != null && k < n/2)welche Mittel in der ifinvertSetist immer, falsewas bedeutet, dass Logik nie verwendet wird.
NetMage
4
Ausgehend von der Antwort von @ ers sollte dies sicher sein, wenn man sich über mögliche unterschiedliche Implementierungen von OrderBy Sorgen macht:
// Instead of thisYourList.OrderBy(x => rnd.Next()).Take(5)// Temporarily transform YourList.Select(v =>new{v, i = rnd.Next()})// Associate a random index to each entry.OrderBy(x => x.i).Take(5)// Sort by (at this point fixed) random index .Select(x => x.v);// Go back to enumerable of entry
Dies ist das Beste, was ich mir bei einem ersten Schnitt einfallen lassen konnte:
publicList<String> getRandomItemsFromList(int returnCount,List<String>list){List<String> returnList =newList<String>();Dictionary<int,int> randoms =newDictionary<int,int>();while(randoms.Count!= returnCount){//generate new random between one and total list countint randomInt =newRandom().Next(list.Count);// store this in dictionary to ensure uniquenesstry{
randoms.Add(randomInt, randomInt);}catch(ArgumentException aex){Console.Write(aex.Message);}//we can assume this element exists in the dictonary already //check for randoms length and then iterate through the original list //adding items we select via random to the return listif(randoms.Count== returnCount){foreach(int key in randoms.Keys)
returnList.Add(list[randoms[key]]);break;//break out of _while_ loop}}return returnList;}
Es schien der beste Weg zu sein, eine Liste von Zufälligkeiten in einem Bereich von 1 - Gesamtanzahl der Listen zu verwenden und dann einfach diese Elemente in die Liste zu ziehen, aber ich denke immer noch darüber nach, das Wörterbuch zu verwenden, um die Eindeutigkeit sicherzustellen.
Beachten Sie auch, dass ich eine Zeichenfolgenliste verwendet habe, die bei Bedarf ersetzt wird.
Die einfache Lösung, die ich verwende (wahrscheinlich nicht gut für große Listen): Kopieren Sie die Liste in eine temporäre Liste, wählen Sie dann in einer Schleife zufällig Element aus der temporären Liste aus und fügen Sie es in die Liste der ausgewählten Elemente ein, während Sie es aus der temporären Liste entfernen (so kann es nicht sein) wiedergewählt).
Beispiel:
List<Object> temp =OriginalList.ToList();List<Object> selectedItems =newList<Object>();Random rnd =newRandom();Object o;int i =0;while(i <NumberOfSelectedItems){
o = temp[rnd.Next(temp.Count)];
selectedItems.Add(o);
temp.Remove(o);
i++;}
Das Entfernen aus der Mitte einer Liste ist so oft kostspielig. Sie können eine verknüpfte Liste für einen Algorithmus verwenden, der so viele Entfernungen erfordert. Oder ersetzen Sie das entfernte Element entsprechend durch einen Nullwert, aber dann werden Sie ein wenig verprügeln, wenn Sie bereits entfernte Elemente auswählen und erneut auswählen müssen.
Paul Chernoch
3
Hier haben Sie eine Implementierung basierend auf Fisher-Yates Shuffle, deren Algorithmuskomplexität O (n) ist, wobei n die Teilmenge oder Stichprobengröße anstelle der Listengröße ist, wie John Shedletsky hervorhob.
publicstaticIEnumerable<T>GetRandomSample<T>(thisIList<T>list,int sampleSize){if(list==null)thrownewArgumentNullException("list");if(sampleSize >list.Count)thrownewArgumentException("sampleSize may not be greater than list count","sampleSize");var indices =newDictionary<int,int>();int index;var rnd =newRandom();for(int i =0; i < sampleSize; i++){int j = rnd.Next(i,list.Count);if(!indices.TryGetValue(j,out index)) index = j;yieldreturnlist[index];if(!indices.TryGetValue(i,out index)) index = i;
indices[j]= index;}}
Dim ar AsNewArrayListDim numToGet AsInteger=5'hard code just to test
ar.Add("12")
ar.Add("11")
ar.Add("10")
ar.Add("15")
ar.Add("16")
ar.Add("17")Dim randomListOfProductIds AsNewArrayListDim toAdd AsString=""For i =0To numToGet -1
toAdd = ar(CInt((ar.Count-1)*Rnd()))
randomListOfProductIds.Add(toAdd)'removefrom id list
ar.Remove(toAdd)Next'sorry i'm lazy and have to write vb at work :( and didn't feel like converting to c#
Ziel: Wählen Sie N Elemente aus der Sammlungsquelle ohne Duplizierung aus. Ich habe eine Erweiterung für jede generische Sammlung erstellt. So habe ich es gemacht:
publicstaticclassCollectionExtension{publicstaticIList<TSource>RandomizeCollection<TSource>(thisIList<TSource> source,int maxItems){int randomCount = source.Count> maxItems ? maxItems : source.Count;int?[] randomizedIndices =newint?[randomCount];Random random =newRandom();for(int i =0; i < randomizedIndices.Length; i++){int randomResult =-1;while(randomizedIndices.Contains((randomResult = random.Next(0, source.Count)))){//0 -> since all list starts from index 0; source.Count -> maximum number of items that can be randomize//continue looping while the generated random number is already in the list of randomizedIndices}
randomizedIndices[i]= randomResult;}IList<TSource> result =newList<TSource>();foreach(int index in randomizedIndices)
result.Add(source.ElementAt(index));return result;}}
Ich habe dies kürzlich bei meinem Projekt mit einer Idee gemacht, die Tylers Punkt 1 ähnelt .
Ich habe eine Reihe von Fragen geladen und zufällig fünf ausgewählt. Die Sortierung wurde mit einem IComparer erreicht .
aAlle Fragen wurden in die a QuestionSorter-Liste geladen, die dann mit der Sortierfunktion der Liste sortiert wurde und die ersten k Elemente ausgewählt wurden.
List<QuestionSorter> unsortedQuestions =newList<QuestionSorter>();// add the questions here
unsortedQuestions.Sort(unsortedQuestions asIComparer<QuestionSorter>);// select the first k elements
Es sollte in O (K) anstelle von O (N) ausgeführt werden, wobei K die Anzahl der gewünschten Elemente und N die Größe der Liste ist, aus der Sie auswählen können:
public<T>List<T> take(List<T> source,int k){int n = source.size();if(k > n){thrownewIllegalStateException("Can not take "+ k +" elements from a list with "+ n +" elements");}List<T> result =newArrayList<T>(k);Map<Integer,Integer> used =newHashMap<Integer,Integer>();int metric =0;for(int i =0; i < k; i++){int off = random.nextInt(n - i);while(true){
metric++;Integer redirect = used.put(off, n - i -1);if(redirect ==null){break;}
off = redirect;}
result.add(source.get(off));}
assert metric <=2*k;return result;}
Dies ist nicht so elegant oder effizient wie die akzeptierte Lösung, aber es ist schnell zu schreiben. Permutieren Sie zuerst das Array zufällig und wählen Sie dann die ersten K Elemente aus. In Python,
import numpy
N =20
K =5
idx = np.arange(N)
numpy.random.shuffle(idx)
print idx[:K]
Wenn N sehr groß ist, kann die normale Methode, die die N Zahlen zufällig mischt und beispielsweise die ersten k Zahlen auswählt, aufgrund der Komplexität des Raums unerschwinglich sein. Der folgende Algorithmus benötigt nur O (k) für zeitliche und räumliche Komplexität.
def random_selection_indices(num_samples, N):
modified_entries ={}
seq =[]for n in xrange(num_samples):
i = N - n -1
j = random.randrange(i)# swap a[j] and a[i]
a_j = modified_entries[j]if j in modified_entries else j
a_i = modified_entries[i]if i in modified_entries else i
if a_i != j:
modified_entries[j]= a_i
elif j in modified_entries:# no need to store the modified value if it is the same as index
modified_entries.pop(j)if a_j != i:
modified_entries[i]= a_j
elif i in modified_entries:# no need to store the modified value if it is the same as index
modified_entries.pop(i)
seq.append(a_j)return seq
Für meinen Gebrauch hatte ich eine Liste mit 100.000 Elementen, und weil sie aus einer Datenbank gezogen wurden, halbierte ich (oder besser) die Zeit im Vergleich zu einem rnd auf der gesamten Liste.
Eine große Liste verringert die Wahrscheinlichkeit von Duplikaten erheblich.
Diese Lösung kann wiederholte Elemente haben !! Der Zufall in der Lochliste darf nicht.
AxelWass
Hmm. Wahr. Wo ich es benutze, spielt das allerdings keine Rolle. Die Antwort wurde bearbeitet, um dies widerzuspiegeln.
Wolf5
-1
Dies wird Ihr Problem lösen
var entries=newList<T>();var selectedItems =newList<T>();for(var i =0; i !=10; i++){var rdm =newRandom().Next(entries.Count);while(selectedItems.Contains(entries[rdm]))
rdm =newRandom().Next(entries.Count);
selectedItems.Add(entries[rdm]);}
Während dies die Frage beantworten könnte, sollten Sie Ihre Antwort so bearbeiten , dass sie eine Erklärung enthält, wie dieser Codeblock die Frage beantwortet. Dies hilft, den Kontext bereitzustellen, und macht Ihre Antwort für zukünftige Leser viel nützlicher.
Antworten:
Durchlaufen und für jedes Element die Wahrscheinlichkeit der Auswahl festlegen = (benötigte Anzahl) / (verbleibende Anzahl)
Wenn Sie also 40 Artikel hätten, hätte der erste eine Chance von 5/40, ausgewählt zu werden. Wenn dies der Fall ist, hat der nächste eine Chance von 4/39, andernfalls eine Chance von 5/39. Wenn Sie am Ende angekommen sind, haben Sie Ihre 5 Gegenstände, und oft haben Sie alle vorher.
quelle
Verwenden von linq:
quelle
YourList
es viele Artikel gibt, aber Sie möchten nur einige auswählen. In diesem Fall ist dies keine effiziente Methode.quelle
Dies ist tatsächlich ein schwierigeres Problem, als es sich anhört, hauptsächlich weil viele mathematisch korrekte Lösungen es Ihnen nicht ermöglichen, alle Möglichkeiten zu nutzen (mehr dazu weiter unten).
Hier sind zunächst einige einfach zu implementierende, korrekte, wenn Sie einen wirklich zufälligen Zahlengenerator haben:
(0) Kyles Antwort ist O (n).
(1) Generieren Sie eine Liste von n Paaren [(0, Rand), (1, Rand), (2, Rand), ...], sortieren Sie sie nach der zweiten Koordinate und verwenden Sie das erste k (für Sie k = 5) Indizes, um Ihre zufällige Teilmenge zu erhalten. Ich denke, das ist einfach zu implementieren, obwohl es O (n log n) Zeit ist.
(2) Initiiere eine leere Liste s = [], die zu den Indizes von k zufälligen Elementen wird. Wählen Sie zufällig eine Zahl r in {0, 1, 2, ..., n-1}, r = rand% n, und addieren Sie diese zu s. Als nächstes nimm r = rand% (n-1) und stecke in s; Fügen Sie zu r die # Elemente weniger als in s hinzu, um Kollisionen zu vermeiden. Nehmen Sie als nächstes r = rand% (n-2) und machen Sie dasselbe usw., bis Sie k verschiedene Elemente in s haben. Dies hat die Worst-Case-Laufzeit O (k ^ 2). Für k << n kann dies also schneller sein. Wenn Sie s sortiert halten und verfolgen, welche zusammenhängenden Intervalle es hat, können Sie es in O (k log k) implementieren, aber es ist mehr Arbeit.
@ Kyle - du hast recht, beim zweiten Gedanken stimme ich deiner Antwort zu. Ich habe es zuerst hastig gelesen und fälschlicherweise gedacht, Sie würden nacheinander jedes Element mit fester Wahrscheinlichkeit k / n auswählen, was falsch gewesen wäre - aber Ihr adaptiver Ansatz erscheint mir richtig. Das tut mir leid.
Ok, und jetzt zum Kicker: asymptotisch (für festes k, n Wachstum) gibt es n ^ k / k! Auswahl der k-Element-Teilmenge aus n Elementen [dies ist eine Annäherung an (n wähle k)]. Wenn n groß und k nicht sehr klein ist, sind diese Zahlen riesig. Die beste Zykluslänge, auf die Sie in einem Standard-32-Bit-Zufallszahlengenerator hoffen können, ist 2 ^ 32 = 256 ^ 4. Wenn wir also eine Liste mit 1000 Elementen haben und zufällig 5 auswählen möchten, kann ein Standard-Zufallszahlengenerator auf keinen Fall alle Möglichkeiten nutzen. Solange Sie jedoch mit einer Auswahl einverstanden sind, die für kleinere Mengen gut funktioniert und immer zufällig "aussieht", sollten diese Algorithmen in Ordnung sein.
Nachtrag : Nachdem ich dies geschrieben hatte, wurde mir klar, dass es schwierig ist, Idee (2) richtig umzusetzen, deshalb wollte ich diese Antwort klarstellen. Um die O (k log k) -Zeit zu erhalten, benötigen Sie eine Array-ähnliche Struktur, die O (log m) -Suchen und Einfügungen unterstützt - ein ausgeglichener Binärbaum kann dies tun. Verwenden Sie eine solche Struktur, um ein Array namens s aufzubauen. Hier ist ein Pseudopython:
Ich schlage vor, einige Beispielfälle durchzugehen, um zu sehen, wie dies die obige englische Erklärung effizient umsetzt.
quelle
Ich denke, die ausgewählte Antwort ist richtig und ziemlich süß. Ich habe es allerdings anders implementiert, da ich das Ergebnis auch in zufälliger Reihenfolge haben wollte.
quelle
Ich bin gerade auf dieses Problem gestoßen, und einige weitere Google-Suchanfragen haben mich zu dem Problem gebracht, eine Liste zufällig zu mischen: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
Um Ihre Liste (zufällig) vollständig zufällig zu mischen, gehen Sie folgendermaßen vor:
So mischen Sie ein Array a von n Elementen (Indizes 0..n-1):
Wenn Sie nur die ersten 5 Elemente benötigen, müssen Sie i nicht von n-1 bis 1 ausführen, sondern nur n-5 (dh: n-5).
Nehmen wir an, Sie brauchen k Gegenstände,
Dies wird:
Jedes ausgewählte Element wird gegen Ende des Arrays ausgetauscht, sodass die ausgewählten k Elemente die letzten k Elemente des Arrays sind.
Dies dauert Zeit O (k), wobei k die Anzahl der zufällig ausgewählten Elemente ist, die Sie benötigen.
Wenn Sie Ihre ursprüngliche Liste nicht ändern möchten, können Sie alle Ihre Swaps in eine temporäre Liste eintragen, diese Liste umkehren und erneut anwenden. Auf diese Weise können Sie den umgekehrten Satz von Swaps ausführen und Ihre ursprüngliche Liste ohne Änderung zurückgeben die O (k) Laufzeit.
Wenn Sie für den echten Stickler (n == k) sind, sollten Sie bei 1 und nicht bei nk anhalten, da die zufällig ausgewählte Ganzzahl immer 0 ist.
quelle
Sie können dies verwenden, aber die Bestellung erfolgt auf Kundenseite
quelle
Von Drachen im Algorithmus , eine Interpretation in C #:
Dieser Algorithmus wählt eindeutige Anzeigen der Elementliste aus.
quelle
var
inneeded
undavailable
beide Ganzzahlen sind, wasneeded/available
immer 0 ergibt .Die Auswahl von N zufälligen Elementen aus einer Gruppe sollte nichts mit der Bestellung zu tun haben ! Bei Zufälligkeit geht es um Unvorhersehbarkeit und nicht darum, Positionen in einer Gruppe zu mischen. Alle Antworten, die sich mit einer Art Bestellung befassen, sind weniger effizient als diejenigen, die dies nicht tun. Da Effizienz hier der Schlüssel ist, werde ich etwas veröffentlichen, das die Reihenfolge der Artikel nicht zu sehr ändert.
1) Wenn Sie echte Zufallswerte benötigen , was bedeutet, dass es keine Einschränkung gibt, aus welchen Elementen Sie auswählen können (dh sobald das ausgewählte Element erneut ausgewählt werden kann):
Wenn Sie das Ausnahmeflag deaktivieren, können Sie beliebig oft zufällige Elemente auswählen.
Dies sollte ziemlich schnell gehen, da es nichts zu überprüfen gibt.
2) Wenn Sie einzelne Mitglieder aus der Gruppe ohne Wiederholung benötigen , würde ich mich auf ein Wörterbuch verlassen (wie viele bereits betont haben).
Der Code ist hier etwas länger als bei anderen Wörterbuchansätzen, da ich ihn nicht nur hinzufüge, sondern auch aus der Liste entferne, also sind es irgendwie zwei Schleifen. Sie können hier sehen, dass ich überhaupt nichts nachbestellt habe, wenn es
count
gleich wirdsource.Count
. Das liegt daran, dass ich glaube, dass Zufälligkeit im gesamten zurückgegebenen Set enthalten sein sollte . Ich meine , wenn Sie wollen 5 zufällige Elemente aus1, 2, 3, 4, 5
, sollte es keine Rolle , ob seine1, 3, 4, 2, 5
oder1, 2, 3, 4, 5
, aber wenn Sie benötigen 4 Elemente aus dem gleichen Satz, dann sollte es unvorhersehbar Ausbeute in1, 2, 3, 4
,1, 3, 5, 2
,2, 3, 5, 4
usw. Zweitens , wenn die Anzahl der zufälligen Elemente sein zurückgegeben wird mehr als die Hälfte der ursprünglichen Gruppe, dann ist es einfacher zu entfernensource.Count - count
Elemente aus der Gruppe als Hinzufügen voncount
Elementen. Aus Leistungsgründen habe ichsource
stattdessen verwendetsourceDict
, um dann einen zufälligen Index in der Methode remove zu erhalten.3) Wenn Sie wirklich unterschiedliche Zufallswerte aus Ihrer Gruppe benötigen, indem Sie die Duplikate in der ursprünglichen Gruppe berücksichtigen, können Sie den gleichen Ansatz wie oben verwenden, aber a
HashSet
ist leichter als ein Wörterbuch.Die
randoms
Variable wird erstelltHashSet
, um zu vermeiden, dass in den seltensten Fällen Duplikate hinzugefügt werden, in denenRandom.Next
der gleiche Wert erzielt werden kann, insbesondere wenn die Eingabeliste klein ist.Einige der Erweiterungsmethoden, die ich verwendet habe:
Wenn es um Leistung geht, bei der Zehntausende von Elementen in der Liste 10000 Mal wiederholt werden müssen, möchten Sie vielleicht eine schnellere Zufallsklasse als
System.Random
, aber ich denke nicht, dass dies eine große Sache ist, wenn man bedenkt, dass letztere höchstwahrscheinlich niemals eine ist Engpass, es ist ziemlich schnell genug ..Bearbeiten: Wenn Sie auch die Reihenfolge der zurückgegebenen Artikel neu ordnen müssen, gibt es nichts, was Dhakims Fisher-Yates-Ansatz übertreffen könnte - kurz, süß und einfach.
quelle
Ich habe über einen Kommentar von @JohnShedletsky zu der akzeptierten Antwort bezüglich (Paraphrase) nachgedacht :
Grundsätzlich sollten Sie in der Lage sein,
subset
zufällige Indizes zu generieren und diese dann aus der ursprünglichen Liste zu entfernen.Die Methode
Wenn Sie noch effizienter sein möchten, würden Sie wahrscheinlich einen
HashSet
der Indizes verwenden , nicht die tatsächlichen Listenelemente (falls Sie komplexe Typen oder teure Vergleiche haben).Der Unit Test
Und um sicherzustellen, dass wir keine Kollisionen usw. haben.
quelle
Ich habe mehrere der oben genannten Antworten kombiniert, um eine von Lazily evaluierte Erweiterungsmethode zu erstellen. Meine Tests haben gezeigt, dass Kyles Ansatz (Reihenfolge (N)) um ein Vielfaches langsamer ist als die Verwendung eines Satzes durch drzaus, um die zu wählenden Zufallsindizes vorzuschlagen (Reihenfolge (K)). Ersteres führt viel mehr Aufrufe an den Zufallszahlengenerator durch und iteriert mehrmals über die Elemente.
Die Ziele meiner Implementierung waren:
1) Verwirklichen Sie nicht die vollständige Liste, wenn Sie eine IEnumerable angeben, die keine IList ist. Wenn ich eine Folge von zig Elementen erhalte, möchte ich nicht über genügend Speicher verfügen. Verwenden Sie Kyles Ansatz für eine Online-Lösung.
2) Wenn ich feststellen kann, dass es sich um eine IList handelt, verwenden Sie den Ansatz von drzaus mit einer Wendung. Wenn K mehr als die Hälfte von N ist, riskiere ich einen Schlag, da ich immer wieder viele zufällige Indizes auswähle und sie überspringen muss. Daher erstelle ich eine Liste der Indizes, die NICHT aufbewahrt werden sollen.
3) Ich garantiere, dass die Artikel in der Reihenfolge zurückgegeben werden, in der sie angetroffen wurden. Kyles Algorithmus erforderte keine Änderung. Der Algorithmus von drzaus erforderte, dass ich keine Elemente in der Reihenfolge aussende, in der die Zufallsindizes ausgewählt wurden. Ich sammle alle Indizes in einem SortedSet und gebe dann Elemente in sortierter Indexreihenfolge aus.
4) Wenn K im Vergleich zu N groß ist und ich den Sinn der Menge invertiere, zähle ich alle Elemente auf und teste, ob der Index nicht in der Menge ist. Dies bedeutet, dass ich die Laufzeit der Bestellung (K) verliere, aber da K in diesen Fällen nahe bei N liegt, verliere ich nicht viel.
Hier ist der Code:
Ich verwende einen speziellen Zufallszahlengenerator, aber Sie können einfach C # 's Random verwenden, wenn Sie möchten. ( FastRandom wurde von Colin Green geschrieben und ist Teil von SharpNEAT. Es hat eine Periode von 2 ^ 128-1, was besser ist als bei vielen RNGs.)
Hier sind die Unit-Tests:
quelle
if (itemsList != null && k < n/2)
welche Mittel in derif
invertSet
ist immer,false
was bedeutet, dass Logik nie verwendet wird.Ausgehend von der Antwort von @ ers sollte dies sicher sein, wenn man sich über mögliche unterschiedliche Implementierungen von OrderBy Sorgen macht:
quelle
Dies ist das Beste, was ich mir bei einem ersten Schnitt einfallen lassen konnte:
Es schien der beste Weg zu sein, eine Liste von Zufälligkeiten in einem Bereich von 1 - Gesamtanzahl der Listen zu verwenden und dann einfach diese Elemente in die Liste zu ziehen, aber ich denke immer noch darüber nach, das Wörterbuch zu verwenden, um die Eindeutigkeit sicherzustellen.
Beachten Sie auch, dass ich eine Zeichenfolgenliste verwendet habe, die bei Bedarf ersetzt wird.
quelle
Die einfache Lösung, die ich verwende (wahrscheinlich nicht gut für große Listen): Kopieren Sie die Liste in eine temporäre Liste, wählen Sie dann in einer Schleife zufällig Element aus der temporären Liste aus und fügen Sie es in die Liste der ausgewählten Elemente ein, während Sie es aus der temporären Liste entfernen (so kann es nicht sein) wiedergewählt).
Beispiel:
quelle
Hier haben Sie eine Implementierung basierend auf Fisher-Yates Shuffle, deren Algorithmuskomplexität O (n) ist, wobei n die Teilmenge oder Stichprobengröße anstelle der Listengröße ist, wie John Shedletsky hervorhob.
quelle
Basierend auf Kyles Antwort ist hier meine c # -Implementierung.
quelle
Diese Methode kann der von Kyle entsprechen.
Angenommen, Ihre Liste hat die Größe n und Sie möchten k Elemente.
Klappt wunderbar :)
-Alex Gilbert
quelle
warum nicht so etwas:
quelle
Es ist viel schwieriger als man denkt. Siehe den großartigen Artikel "Shuffling" von Jeff.
Ich habe einen sehr kurzen Artikel zu diesem Thema geschrieben, der C # -Code enthält:
Zufällige Teilmenge von N Elementen eines bestimmten Arrays zurückgeben
quelle
Ziel: Wählen Sie N Elemente aus der Sammlungsquelle ohne Duplizierung aus. Ich habe eine Erweiterung für jede generische Sammlung erstellt. So habe ich es gemacht:
quelle
Ich habe dies kürzlich bei meinem Projekt mit einer Idee gemacht, die Tylers Punkt 1 ähnelt .
Ich habe eine Reihe von Fragen geladen und zufällig fünf ausgewählt. Die Sortierung wurde mit einem IComparer erreicht .
aAlle Fragen wurden in die a QuestionSorter-Liste geladen, die dann mit der Sortierfunktion der Liste sortiert wurde und die ersten k Elemente ausgewählt wurden.
Verwendung:
quelle
Hier ist mein Ansatz (Volltext hier http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).
Es sollte in O (K) anstelle von O (N) ausgeführt werden, wobei K die Anzahl der gewünschten Elemente und N die Größe der Liste ist, aus der Sie auswählen können:
quelle
Dies ist nicht so elegant oder effizient wie die akzeptierte Lösung, aber es ist schnell zu schreiben. Permutieren Sie zuerst das Array zufällig und wählen Sie dann die ersten K Elemente aus. In Python,
quelle
Ich würde eine Erweiterungsmethode verwenden.
quelle
Speicher: ~ count
Komplexität: O (count 2 )
quelle
Wenn N sehr groß ist, kann die normale Methode, die die N Zahlen zufällig mischt und beispielsweise die ersten k Zahlen auswählt, aufgrund der Komplexität des Raums unerschwinglich sein. Der folgende Algorithmus benötigt nur O (k) für zeitliche und räumliche Komplexität.
http://arxiv.org/abs/1512.00501
quelle
Verwenden von LINQ mit großen Listen (wenn es teuer ist, jedes Element zu berühren) UND wenn Sie mit der Möglichkeit von Duplikaten leben können:
Für meinen Gebrauch hatte ich eine Liste mit 100.000 Elementen, und weil sie aus einer Datenbank gezogen wurden, halbierte ich (oder besser) die Zeit im Vergleich zu einem rnd auf der gesamten Liste.
Eine große Liste verringert die Wahrscheinlichkeit von Duplikaten erheblich.
quelle
Dies wird Ihr Problem lösen
quelle