Wählen Sie N zufällige Elemente aus einer Liste<T> in C#
https://stackoverflow.com/questions/48087
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich brauche einen schnellen Algorithmus zu wählen Sie 5 zufällige Elemente aus einer generischen Liste.Zum Beispiel würde ich gerne erhalten Sie 5 zufällige Elemente aus einer List<string>.
Lösung
Durchlaufen und für jedes element die Wahrscheinlichkeit, Auswahl = (number needed)/(Anzahl Links)
Also, wenn Sie hatte über 40 Gegenstände, die erste wäre eine 5/40 chance, ausgewählt zu werden.Wenn es ist, der nächste hat eine 4/39 chance, ansonsten hat es eine 5/39 chance.Durch die Zeit, die Sie am Ende bekommen Sie Ihr 5 Gegenstände, und oft werden Sie haben, alle von Ihnen vor.
Andere Tipps
Mit linq:
YourList.OrderBy(x => rnd.Next()).Take(5)
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}
Dies ist eigentlich ein größere problem, als es klingt, vor allem, weil viele mathematisch korrekte Lösungen werden nicht tatsächlich können Sie schlagen Sie alle Möglichkeiten (mehr dazu weiter unten).
Erstens, hier sind einige einfach zu implementierende und korrigieren-wenn-Sie-haben-eine-wirklich-random-number generator:
(0) Kyle Antwort, das ist O(n).
(1) Erzeugen Sie eine Liste von n Paaren [(0, rand), (1, rand), (2, rand)...], Sie zu Sortieren, indem Sie die zweite Koordinate und die erste k (für k=5) Indizes zu bekommen, die zufälligen Teilmenge.Ich denke, dies ist einfach zu implementieren, obwohl es ist O(n log n) Zeit.
(2) Init einem leeren Liste s = [] wird wachsen, um die Indizes von k Elementen.Wählen Sie eine Zahl r in {0, 1, 2, ..., n-1} zufällig, r = rand % n, und fügen Sie diese an en.Als Nächstes nehmen Sie r = rand % (n-1) und stick in s;hinzufügen, um r die # Elemente weniger, als es in s, um Kollisionen zu vermeiden.Als Nächstes nehmen Sie r = rand % (n-2), und tun das gleiche, etc.bis man k verschiedene Elemente in s.Dies hat worst-case-Laufzeit O(k^2).Also für k << n dies kann schneller sein.Wenn Sie halten die s sortiert und track, die zusammenhängende Intervalle, die es hat, können Sie es implementieren in O(k log k), aber es ist mehr Arbeit.
@Kyle - du hast Recht, am zweiten dachte ich Stimme mit Ihrer Antwort.Ich hastig es zuerst gelesen und fälschlicherweise dachte, Sie waren, die angibt, um nacheinander wählen Sie jedes element mit fester Wahrscheinlichkeit k/n, das wäre falsch gewesen -, aber Ihre " adaptive Ansatz scheint richtig zu mir.Das tut uns Leid.
Ok, und jetzt der Clou:asymptotisch (für Feste k, n wachsen), es n^k/k!Entscheidungen des k-element-Teilmenge aus n Elementen [dies ist eine Näherung der (n choose k)].Wenn n groß ist und k ist nicht sehr klein ist, dann werden diese zahlen sind riesig.Die besten Zyklus-Länge, die Sie für hoffen können, in jedem standard-32-bit random number generator ist 2^32 = 256^4.Wenn wir also eine Liste von 1000 Elementen, und wir wählen die 5 zufällig, es gibt keine Möglichkeit, ein standard random number generator schlagen Sie alle Möglichkeiten.Allerdings, so lange wie Sie sind ok mit einer Auswahl, die funktioniert gut für kleinere Mengen, und immer wieder "sieht" zufällig, dann werden diese algorithmen sollten in Ordnung sein.
Nachtrag:Nach diesem schreiben, erkannte ich, dass es schwierig umzusetzende Idee (2) richtig, also wollte ich zur Klärung dieser Antwort.Bekommen O(k log k) Zeit, Sie benötigen eine array-ähnliche Struktur, die unterstützt O(log m) sucht und Beilagen - ein ausgewogener binärer Baum kann dies tun.Über eine solche Struktur aufzubauen, ein array mit dem Namen s, hier ist einige 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, das laufen durch ein paar Beispiel-Fälle zu sehen, wie diese effizient implementiert die oben genannten englische Erklärung.
Ich denke, die ausgewählte Antwort richtig ist und ziemlich süß.Implementiert habe ich das anders, obwohl, wie ich wollte, dass das Ergebnis in zufälliger Reihenfolge.
static IEnumerable<SomeType> PickSomeInRandomOrder<SomeType>(
IEnumerable<SomeType> someTypes,
int maxCount)
{
Random random = new Random(DateTime.Now.Millisecond);
Dictionary<double, SomeType> randomSortTable = new Dictionary<double,SomeType>();
foreach(SomeType someType in someTypes)
randomSortTable[random.NextDouble()] = someType;
return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);
}
Ich nur lief in dieses problem, und einige weitere google-Suche brachte mich auf das problem der zufällig mischen Sie eine Liste: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
Völlig zufällig shuffle Ihre Liste (in place) Sie dies tun:
Shuffle ein array a von n Elementen (die Indizes 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
Wenn Sie nur die ersten 5 Elemente, dann, anstatt ich den ganzen Weg von n-1 bis 1, Sie müssen nur run es-n-5 (ie:n-5)
Können sagen, Sie müssen k Elemente,
Das wird zu:
for (i = n − 1; i >= n-k; i--)
{
j = random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
}
Jedes Element, das ausgewählt wird getauscht gegen Ende des Arrays, also die k Elemente ausgewählt sind die letzten k Elemente des Arrays.
Das kostet Zeit O(k), wobei k die Anzahl der zufällig ausgewählten Elemente, die Sie brauchen.
Weiter, wenn Sie nicht wollen, ändern Sie Ihre erste Liste, Sie können schreiben unten alle Ihre swaps in eine temporäre Liste, reverse-Liste und wenden Sie Sie erneut, damit die Durchführung der inversen Reihe von swaps und Rückgabe, die Sie Ihrer ursprünglichen Liste ohne änderung der O(k) Zeit läuft.
Schließlich, für die real stickler, wenn (n == k), Sie sollten aufhören, auf 1, nicht n-k, da die zufällig gewählte ganze Zahl wird immer 0 sein.
Sie können dies verwenden, aber die Bestellung wird geschehen auf der client-Seite
.AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
Von Drachen in den Algorithmus, eine interpretation, die in C#:
int k = 10; // items to select
var items = new List<int>(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 });
var selected = new List<int>();
double needed = k;
double available = items.Count;
var rand = new Random();
while (selected.Count < k) {
if( rand.NextDouble() < needed / available ) {
selected.Add(items[(int)available-1])
needed--;
}
available--;
}
Dieser Algorithmus wählt eindeutige Indizes der Elemente-Liste.
Dachte über die Bemerkung von @JohnShedletsky auf die akzeptierte Antwort in Bezug auf (paraphrase):
Sie sollten in der Lage sein, dies in O(Teilmenge.Länge), sondern O(originalList.Länge)
Grundsätzlich sollten Sie in der Lage sein zu generieren subset zufällige Indizes und dann zupfen Sie Sie aus der ursprünglichen Liste.
Die Methode
public static class EnumerableExtensions {
public static Random randomizer = new Random(); // you'd ideally be able to replace this with whatever makes you comfortable
public static IEnumerable<T> GetRandom<T>(this IEnumerable<T> list, int numItems) {
return (list as 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 confusing
public static IEnumerable<T> GetRandom<T>(this T[] list, int numItems) {
var items = new HashSet<T>(); // don't want to add the same item twice; otherwise use a list
while (numItems > 0 )
// if we successfully added it, move on
if( items.Add(list[randomizer.Next(list.Length)]) ) numItems--;
return items;
}
// and because it's really fun; note -- you may get repetition
public static IEnumerable<T> PluckRandomly<T>(this IEnumerable<T> list) {
while( true )
yield return list.ElementAt(randomizer.Next(list.Count()));
}
}
Wenn Sie wollte, noch effizienter, würden Sie wahrscheinlich ein HashSet der Indizes, nicht die eigentlichen Listenelemente (im Fall du hast komplexe Typen oder teure Vergleiche);
Der Unit-Test
Und zu machen sicher, dass wir haben keine Kollisionen, etc.
[TestClass]
public class RandomizingTests : UnitTestBase {
[TestMethod]
public void GetRandomFromList() {
this.testGetRandomFromList((list, num) => list.GetRandom(num));
}
[TestMethod]
public void PluckRandomly() {
this.testGetRandomFromList((list, num) => list.PluckRandomly().Take(num), requireDistinct:false);
}
private void 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);
}
}
}
Auswahl N random Elemente aus einer Gruppe sollte nichts zu tun haben mit Bestellung!Zufälligkeit über die Unberechenbarkeit und nicht über das mischen Positionen in einer Gruppe.Alle Antworten auf, die sich einige ein bisschen Bestellung gebunden ist, weniger effizient zu sein als diejenigen, die dies nicht tun.Da der Wirkungsgrad ist hier der Schlüssel, werde ich etwas posten, das nicht die Reihenfolge der Elemente ändern zu viel.
1) Wenn Sie benötigen true zufällige Werte, die bedeutet, es ist keine Einschränkung auf die Elemente zu wählen (dh einmal ausgewählt werden kann reselected):
public static List<T> GetTrueRandom<T>(this IList<T> source, int count,
bool throwArgumentOutOfRangeException = true)
{
if (throwArgumentOutOfRangeException && count > source.Count)
throw new ArgumentOutOfRangeException();
var randoms = new List<T>(count);
randoms.AddRandomly(source, count);
return randoms;
}
Wenn Sie die exception-flag aus, dann können Sie sich zufällige Elemente beliebige Anzahl von Zeiten.
Wenn Sie haben { 1, 2, 3, 4 }, dann kann es geben { 1, 4, 4 }, { 1, 4, 3 } etc für 3 items oder sogar { 1, 4, 3, 2, 4 } für 5 Stück!
Dies sollte Recht schnell gehen, denn es hat nichts, um zu überprüfen.
2) Wenn Sie benötigen einzelnen Mitglieder aus der Gruppe ohne Wiederholung, dann würde ich setzen auf ein Wörterbuch (wie viele betont haben bereits).
public static List<T> GetDistinctRandom<T>(this IList<T> source, int count)
{
if (count > source.Count)
throw new ArgumentOutOfRangeException();
if (count == source.Count)
return new List<T>(source);
var sourceDict = source.ToIndexedDictionary();
if (count > source.Count / 2)
{
while (sourceDict.Count > count)
sourceDict.Remove(source.GetRandomIndex());
return sourceDict.Select(kvp => kvp.Value).ToList();
}
var randomDict = new Dictionary<int, T>(count);
while (randomDict.Count < count)
{
int key = source.GetRandomIndex();
if (!randomDict.ContainsKey(key))
randomDict.Add(key, sourceDict[key]);
}
return randomDict.Select(kvp => kvp.Value).ToList();
}
Der code ist ein wenig länger als andere Wörterbuch Ansätze hier, denn ich bin nicht nur hinzufügen, sondern auch das entfernen aus der Liste, also irgendwie zwei Schleifen.Sie können hier sehen, dass ich nicht Sie nachbestellt überhaupt nichts, wenn count wird gleich source.Count.Das ist, weil ich glaube, Zufälligkeit sollte in der zurückgegeben set insgesamt.Ich meine, wenn Sie möchten 5 zufällige Elemente aus 1, 2, 3, 4, 5, sollte es nicht egal, wenn seine 1, 3, 4, 2, 5 oder 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, 4 etc.Zweitens, wenn die Anzahl der zufällige Elemente zurückgegeben werden mehr als die Hälfte der ursprünglichen Gruppe, die leichter zu entfernen source.Count - count Elemente aus der Gruppe als Zugabe count Elemente.Aus performance-Gründen die ich verwendet habe source statt sourceDict um dann zufällige index in die remove-Methode.
Also, wenn Sie { 1, 2, 3, 4 }, dies kann am Ende in { 1, 2, 3 }, { 3, 4, 1 } etc für 3 Elemente.
3) Wenn brauchen Sie wirklich verschiedene zufällige Werte aus Ihrer Gruppe unter Berücksichtigung der Duplikate in der ursprünglichen Gruppe, dann können Sie den gleichen Ansatz wie oben, aber eine HashSet wird leichter sein als ein Wörterbuch.
public static List<T> GetTrueDistinctRandom<T>(this IList<T> source, int count,
bool throwArgumentOutOfRangeException = true)
{
if (count > source.Count)
throw new ArgumentOutOfRangeException();
var set = new HashSet<T>(source);
if (throwArgumentOutOfRangeException && count > set.Count)
throw new ArgumentOutOfRangeException();
List<T> list = hash.ToList();
if (count >= set.Count)
return list;
if (count > set.Count / 2)
{
while (set.Count > count)
set.Remove(list.GetRandom());
return set.ToList();
}
var randoms = new HashSet<T>();
randoms.AddRandomly(list, count);
return randoms.ToList();
}
Die randoms variable gemacht wird HashSet um Duplikate zu vermeiden, die Hinzugefügt wird, in der seltenste der seltensten den Fällen, wo Random.Next Ausbeute den gleichen Wert, vor allem, wenn input-Liste ist klein.
So { 1, 2, 2, 4 } => 3 random items => { 1, 2, 4 } und nie { 1, 2, 2}
{ 1, 2, 2, 4 } => 4 random items => exception!!oder { 1, 2, 4 } je auf die Flagge gesetzt.
Einige der Erweiterung Methoden, die ich verwendet habe:
static Random rnd = new Random();
public static int GetRandomIndex<T>(this ICollection<T> source)
{
return rnd.Next(source.Count);
}
public static T GetRandom<T>(this IList<T> source)
{
return source[source.GetRandomIndex()];
}
static void AddRandomly<T>(this ICollection<T> toCol, IList<T> fromList, int count)
{
while (toCol.Count < count)
toCol.Add(fromList.GetRandom());
}
public static Dictionary<int, T> ToIndexedDictionary<T>(this IEnumerable<T> lst)
{
return lst.ToIndexedDictionary(t => t);
}
public static Dictionary<int, T> ToIndexedDictionary<S, T>(this IEnumerable<S> lst,
Func<S, T> valueSelector)
{
int index = -1;
return lst.ToDictionary(t => ++index, valueSelector);
}
Wenn its all about performance mit zig 1000de von Elementen in der Liste zu iterieren 10000 mal, dann möchten Sie vielleicht zu haben schneller random-Klasse als System.Random, aber ich glaube nicht, dass das eine große Sache, denn letzteres wahrscheinlich nie einen Engpass, es ist ziemlich schnell genug..
Edit: Wenn Sie müssen re-arrangieren der Reihenfolge der zurückgegebenen Produkte als gut, dann gibt es nichts, schlagen können dhakim Fisher-Yates-Ansatz - kurz, süß und einfach..
Die einfache Lösung, die ich verwenden (wahrscheinlich nicht gut für große Listen):Kopieren Sie die Liste in die temporäre Liste, dann in der Schleife, die nach dem Zufallsprinzip wählen Sie den Menüpunkt aus temp-Liste aus und legen Sie es in die ausgewählten Elemente der Liste beim entfernen aus den temp-Liste (es kann also keine reselected).
Beispiel:
List<Object> temp = OriginalList.ToList();
List<Object> selectedItems = new List<Object>();
Random rnd = new Random();
Object o;
int i = 0;
while (i < NumberOfSelectedItems)
{
o = temp[rnd.Next(temp.Count)];
selectedItems.Add(o);
temp.Remove(o);
i++;
}
Ich kombinierte einige der oben genannten Antworten zu erstellen, die ein Träge ausgewertet extension-Methode.Meine Tests zeigten, dass Kyle 's Ansatz (Um(N)) ist um ein Vielfaches langsamer als drzaus' verwenden Sie für einen Satz vorschlagen, die zufällige Indizes zu wählen (Um(K)).Der ehemalige führt viele mehr anrufen, um den Zufallszahlen-generator, plus iteriert mal mehr über die Elemente.
Die Ziele meiner Umsetzung:
1) erkennen nicht die vollständige Liste, wenn gegeben, eine IEnumerable, dass ist nicht eine IList.Wenn ich eine Sequenz von Myriaden Dingen, die ich nicht wollen, zu laufen aus dem Speicher.Verwenden Kyle ' s Ansatz für eine Online-Lösung.
2) Wenn kann ich sagen, dass es eine IList, verwenden drzaus " - Ansatz, mit einem twist.Wenn K ist mehr als die Hälfte von N, ich riskieren Prügel, wie ich wählen, viele zufällige Indizes wieder und wieder, und überspringen Sie Sie.Ich so verfassen Sie eine Liste der Indizes, um NICHT zu halten.
3) ich garantieren, dass die Elemente zurückgegeben werden in der gleichen Reihenfolge, in der Sie aufgetreten sind.Kyle ' s Algorithmus benötigt keine Veränderung.drzaus' - Algorithmus verlangt, dass ich nicht emittieren Elemente in der Reihenfolge, dass die zufällige Indizes gewählt werden.Ich sammle alle Indizes in einem SortedSet, dann emittieren Elemente in sortierter Reihenfolge des index.
4) Wenn K groß ist im Vergleich zu N und ich umdrehen der Sinn des Satzes, dann erkläre ich Sie alle Elemente und test, wenn der index nicht in der Gruppe.Dies bedeutet, dass Ich verliere die Bestellung(K) - Laufzeit, aber da K in der Nähe N, die in diesen Fällen habe ich nicht viel verlieren.
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>
public static IEnumerable<TElem> TakeRandom<TElem>(this IEnumerable<TElem> items, int k, int n)
{
var r = new FastRandom();
var itemsList = items as IList<TElem>;
if (k >= n || (itemsList != null && k >= itemsList.Count))
foreach (var item in items) yield return 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>) new HashSet<int>() : (ISet<int>) new SortedSet<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))
yield return itemsList[itemIndex];
}
}
else
{
// positions contains all the indices of elements to Take.
foreach (var itemIndex in positions)
yield return 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)
{
yield return item;
found++;
}
scanned++;
if (found >= k || scanned >= n)
break;
}
}
}
}
Ich verwenden Sie ein spezielles random number generator, aber Sie können nur mit C#'s Random wenn Sie wollen.(FastRandom geschrieben wurde von Colin Grün und ist Teil SharpNEAT.Es hat eine Periode von 2^128-1, was besser ist als viele RNGs.)
Hier sind die unit-tests:
[TestClass]
public class TakeRandomTests
{
/// <summary>
/// Ensure that when randomly choosing items from an array, all items are chosen with roughly equal probability.
/// </summary>
[TestMethod]
public void TakeRandom_Array_Uniformity()
{
const int numTrials = 2000000;
const int expectedCount = numTrials/20;
var timesChosen = new int[100];
var century = new int[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]
public void TakeRandom_IEnumerable_Uniformity()
{
const int numTrials = 2000000;
const int expectedCount = numTrials / 20;
var timesChosen = new int[100];
for (var trial = 0; trial < numTrials; trial++)
{
foreach (var i in Range(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));
}
private IEnumerable<int> Range(int low, int count)
{
for (var i = low; i < low + count; i++)
yield return i;
}
private static void AssertBetween(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));
}
private static void AssertBetween(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));
}
}
Hier haben Sie eine Implementierung basierend auf Fisher-Yates Shuffle deren Algorithmus Komplexität ist O(n) wobei n die Teilmenge oder Stichprobenumfang, statt der Liste eine Größe John Shedletsky hingewiesen.
public static IEnumerable<T> GetRandomSample<T>(this IList<T> list, int sampleSize)
{
if (list == null) throw new ArgumentNullException("list");
if (sampleSize > list.Count) throw new ArgumentException("sampleSize may not be greater than list count", "sampleSize");
var indices = new Dictionary<int, int>(); int index;
var rnd = new Random();
for (int i = 0; i < sampleSize; i++)
{
int j = rnd.Next(i, list.Count);
if (!indices.TryGetValue(j, out index)) index = j;
yield return list[index];
if (!indices.TryGetValue(i, out index)) index = i;
indices[j] = index;
}
}
Basierend auf Kyle ' s Antwort, hier ist mein c# - Implementierung.
/// <summary>
/// Picks random selection of available game ID's
/// </summary>
private static List<int> GetRandomGameIDs(int count)
{
var gameIDs = (int[])HttpContext.Current.Application["NonDeletedArcadeGameIDs"];
var totalGameIDs = gameIDs.Count();
if (count > totalGameIDs) count = totalGameIDs;
var rnd = new Random();
var leftToPick = count;
var itemsLeft = totalGameIDs;
var arrPickIndex = 0;
var returnIDs = new List<int>();
while (leftToPick > 0)
{
if (rnd.Next(0, itemsLeft) < leftToPick)
{
returnIDs .Add(gameIDs[arrPickIndex]);
leftToPick--;
}
arrPickIndex++;
itemsLeft--;
}
return returnIDs ;
}
Diese Methode kann als äquivalent zu Kyle hat.
Sagen Sie Ihre Liste der Größe n und Sie möchten die k-Elemente.
Random rand = new Random();
for(int i = 0; k>0; ++i)
{
int r = rand.Next(0, n-i);
if(r<k)
{
//include element i
k--;
}
}
Funktioniert wie ein Charme :)
-Alex Gilbert
Die Ausweitung von @ers s Antwort, wenn man sich sorgen über mögliche Implementierungen von OrderBy, sollte dies sicher sein:
// Instead of this
YourList.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 die beste, die ich gefunden habe auf einer ersten Schnitt:
public List<String> getRandomItemsFromList(int returnCount, List<String> list)
{
List<String> returnList = new List<String>();
Dictionary<int, int> randoms = new Dictionary<int, int>();
while (randoms.Count != returnCount)
{
//generate new random between one and total list count
int randomInt = new Random().Next(list.Count);
// store this in dictionary to ensure uniqueness
try
{
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 list
if (randoms.Count == returnCount)
{
foreach (int key in randoms.Keys)
returnList.Add(list[randoms[key]]);
break; //break out of _while_ loop
}
}
return returnList;
}
Mit Hilfe einer Liste von randoms in einem Bereich von 1 - komplette Liste zählen und dann einfach ziehen die entsprechenden Elemente in der Liste schien der beste Weg zu sein, aber das Wörterbuch verwenden, um die Eindeutigkeit ist etwas, was ich noch grübelte über.
Beachten Sie auch, ich verwendet eine string-Liste, bei Bedarf ersetzen.
warum nicht so etwas wie dieses:
Dim ar As New ArrayList
Dim numToGet As Integer = 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 As New ArrayList
Dim toAdd As String = ""
For i = 0 To numToGet - 1
toAdd = ar(CInt((ar.Count - 1) * Rnd()))
randomListOfProductIds.Add(toAdd)
'remove from 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#
Es ist viel schwieriger, als man denken würde.Siehe die großer Artikel "Shuffling" von Jeff.
Geschrieben habe ich einen sehr kurzen Artikel über dieses Thema, einschließlich der C# - code:
Rückkehr zufällige Teilmenge N Elemente eines gegebenen Arrays
Ziel:Wählen Sie N Anzahl der Elemente Sammlung von der Quelle, ohne Vervielfältigung.Ich habe eine Erweiterung für jede generische Sammlung.Hier ist, wie ich es gemacht habe:
public static class CollectionExtension
{
public static IList<TSource> RandomizeCollection<TSource>(this IList<TSource> source, int maxItems)
{
int randomCount = source.Count > maxItems ? maxItems : source.Count;
int?[] randomizedIndices = new int?[randomCount];
Random random = new Random();
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 = new List<TSource>();
foreach (int index in randomizedIndices)
result.Add(source.ElementAt(index));
return result;
}
}
Ich habe vor kurzem das auf meinem Projekt mit einer Idee ähnlich Tyler ' s point 1.
Ich war be-eine Reihe von Fragen und der Auswahl von fünf nach dem Zufallsprinzip.Die Sortierung wurde durch die Verwendung einer IComparer.
alle Fragen wurden geladen, in der ein QuestionSorter Liste, die dann sortiert mit der Liste der Sort-Funktion und die ersten k Elemente ausgewählt.
private class QuestionSorter : IComparable<QuestionSorter>
{
public double SortingKey
{
get;
set;
}
public Question QuestionObject
{
get;
set;
}
public QuestionSorter(Question q)
{
this.SortingKey = RandomNumberGenerator.RandomDouble;
this.QuestionObject = q;
}
public int CompareTo(QuestionSorter other)
{
if (this.SortingKey < other.SortingKey)
{
return -1;
}
else if (this.SortingKey > other.SortingKey)
{
return 1;
}
else
{
return 0;
}
}
}
Verwendung:
List<QuestionSorter> unsortedQuestions = new List<QuestionSorter>();
// add the questions here
unsortedQuestions.Sort(unsortedQuestions as IComparer<QuestionSorter>);
// select the first k elements
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), wobei K die Anzahl von gewünschten Elementen und N die Größe der Liste zu wählen aus:
public <T> List<T> take(List<T> source, int k) {
int n = source.size();
if (k > n) {
throw new IllegalStateException(
"Can not take " + k +
" elements from a list with " + n +
" elements");
}
List<T> result = new ArrayList<T>(k);
Map<Integer,Integer> used = new HashMap<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 als die akzeptierte Lösung, aber es ist schnell zu schreiben.Erste, permutiert Sie das array nach dem Zufallsprinzip, und wählen Sie dann die ersten K Elemente.In python,
import numpy
N = 20
K = 5
idx = np.arange(N)
numpy.random.shuffle(idx)
print idx[:K]
Ich würde verwenden Sie eine Erweiterung Methode.
public static IEnumerable<T> TakeRandom<T>(this IEnumerable<T> elements, int countToTake)
{
var random = new Random();
var internalList = elements.ToList();
var selected = new List<T>();
for (var i = 0; i < countToTake; ++i)
{
var next = random.Next(0, internalList.Count - selected.Count);
selected.Add(internalList[next]);
internalList[next] = internalList[internalList.Count - selected.Count];
}
return selected;
}
public static IEnumerable<T> GetRandom<T>(this IList<T> list, int count, Random random)
{
// Probably you should throw exception if count > list.Count
count = Math.Min(list.Count, count);
var selectedIndices = new SortedSet<int>();
// Random upper bound
int randomMax = list.Count - 1;
while (selectedIndices.Count < count)
{
int randomIndex = random.Next(0, randomMax);
// skip over already selected indeces
foreach (var selectedIndex in selectedIndices)
if (selectedIndex <= randomIndex)
++randomIndex;
else
break;
yield return list[randomIndex];
selectedIndices.Add(randomIndex);
--randomMax;
}
}
Speicher:~count
Die Komplexität:O(count2)
Wenn N sehr groß ist, wird die normale Methode, die zufällig mischt die N-Nummern und wählt, sagen wir, die ersten k zahlen, können unerschwinglich werden, weil der Speicherplatz-Komplexität.Der folgende Algorithmus benötigt nur O(k) Zeit und Raum Komplexität.
http://arxiv.org/abs/1512.00501
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
Die Verwendung von LINQ mit großen Listen (wenn teuer zu berühren, jedes element), UND wenn Sie Leben können mit der Möglichkeit von Duplikaten:
new int[5].Select(o => (int)(rnd.NextDouble() * maxIndex)).Select(i => YourIEnum.ElementAt(i))
Für meine Verwendung musste ich eine Liste mit 100.000 Elementen, und weil von Ihnen wird gezogen von einer DB, die ich über halfed (oder besser), ist die Zeit im Vergleich zu einem rnd auf die ganze Liste.
Mit einer großen Liste wird reduzieren die Chancen deutlich für Duplikate.
