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

JC Grubbs
quelle
11
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?
Brezel

Antworten:

127

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.

Kyle Cronin
quelle
33
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.
Ilmari Karonen
216

Verwenden von linq:

YourList.OrderBy(x => rnd.Next()).Take(5)
Ers
quelle
2
+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.
Callum Watkins
39
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
    return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}
vag
quelle
27

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.

Tyler
quelle
2
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.

    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);
    }
Frank Schwieterman
quelle
GENIAL! Hat mir wirklich geholfen!
Armstrongest
1
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 1 do
       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.

Dhakim
quelle
Ich habe es mit C # in meinem Blog-Beitrag implementiert : vijayt.com/post/random-select-using-fisher-yates-algorithm . Hoffe, es hilft jemandem, der nach dem C # -Weg sucht.
Vijayst
9

Sie können dies verwenden, aber die Bestellung erfolgt auf Kundenseite

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
Marwan Roushdy
quelle
Einverstanden. Es ist vielleicht nicht die beste oder zufälligste Leistung, aber für die große Mehrheit der Menschen wird dies gut genug sein.
Richiban
Herabgestuft, weil Guids garantiert eindeutig und nicht zufällig sind .
Theodor Zoulias
8

Von Drachen im Algorithmus , eine Interpretation 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 Anzeigen der Elementliste aus.

Spoulson
quelle
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):

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

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

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

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

nawfal
quelle
6

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

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 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]
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);
        }
    }
}
drzaus
quelle
2
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>
    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 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]
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));
    }
}
Paul Chernoch
quelle
Gibt es keinen Fehler im Test? Sie haben if (itemsList != null && k < n/2)welche Mittel in der if invertSetist 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 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
Hardsetting
quelle
3

Dies ist das Beste, was ich mir bei einem ersten Schnitt einfallen lassen konnte:

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

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.

IanStallings
quelle
1
Arbeitete beim ersten Schuss!
Sangam
3

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 = 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++;
 }
Tine M.
quelle
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.

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;
    }
}
Jesús López
quelle
2

Basierend auf Kyles Antwort ist hier meine 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 ;
}
Tom Gullen
quelle
2

Diese Methode kann der von Kyle entsprechen.

Angenommen, Ihre Liste hat die Größe n und Sie möchten 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--;
    }
} 

Klappt wunderbar :)

-Alex Gilbert

Alex Gilbert
quelle
1
Das sieht für mich gleich aus. Vergleichen Sie mit dem ähnlichen stackoverflow.com/a/48141/2449863
DCShannon
1

warum nicht so etwas:

 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#
Cameron A. Ellis
quelle
1

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:

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;
    }
}
Jesse Gador
quelle
0

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.

    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
hitec
quelle
0

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:

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;
}
Kristofer
quelle
0

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]
apdnu
quelle
0

Ich würde eine Erweiterungsmethode verwenden.

    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;
    }
Kvam
quelle
0
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
Komplexität: O (count 2 )

Kardinal
quelle
0

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

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
Dai
quelle
0

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:

new int[5].Select(o => (int)(rnd.NextDouble() * maxIndex)).Select(i => YourIEnum.ElementAt(i))

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.

Wolf5
quelle
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=new List<T>();
var selectedItems = new List<T>();


                for (var i = 0; i !=10; i++)
                {
                    var rdm = new Random().Next(entries.Count);
                        while (selectedItems.Contains(entries[rdm]))
                            rdm = new Random().Next(entries.Count);

                    selectedItems.Add(entries[rdm]);
                }
Cyrille
quelle
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.
Hoppeduppeanut