Wybierz N losowych elementów z List <T> w C #

Potrzebuję szybkiego algorytmu, aby wybrać 5 losowych elementów z ogólnej listy. Na przykład chciałbym uzyskać 5 losowych elementów z pliku List<string>.

Iteruj przez i dla każdego elementu określ prawdopodobieństwo wyboru = (wymagana liczba) / (liczba po lewej)

Więc gdybyś miał 40 elementów, pierwszy miałby 5/40 szans na wybranie. Jeśli tak, następny ma szansę 4/39, w przeciwnym razie ma szansę 5/39. Zanim dojdziesz do końca, będziesz miał 5 przedmiotów, a często będziesz mieć je wszystkie przedtem.

Korzystanie z 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();
}

W rzeczywistości jest to trudniejszy problem, niż się wydaje, głównie dlatego, że wiele matematycznie poprawnych rozwiązań nie pozwoli na trafienie wszystkich możliwości (więcej na ten temat poniżej).

Po pierwsze, oto kilka łatwych do zaimplementowania, poprawnych, jeśli masz-naprawdę-losowy generator liczb:

(0) Odpowiedź Kyle'a, czyli O (n).

(1) Wygeneruj listę n par [(0, rand), (1, rand), (2, rand), ...], posortuj je według drugiej współrzędnej i użyj pierwszego k (dla ciebie, k = 5), aby otrzymać losowy podzbiór. Myślę, że jest to łatwe do wykonania, chociaż jest to czas O (n log n).

(2) Wstaw pustą listę s = [], która będzie stanowić wskaźniki k losowych elementów. Wybierz losowo liczbę r z {0, 1, 2, ..., n-1}, r = rand% n, i dodaj ją do s. Następnie weź r = rand% (n-1) i włóż s; dodaj do r # elementów mniej niż w s, aby uniknąć kolizji. Następnie weź r = rand% (n-2) i zrób to samo, itd., Aż uzyskasz k różnych elementów w s. W najgorszym przypadku czas działania O (k ^ 2). Więc dla k << n może to być szybsze. Jeśli będziesz posortować s i śledzić, które ciągłe przedziały ma, możesz zaimplementować to w O (k log k), ale to więcej pracy.

@Kyle - masz rację, po zastanowieniu zgadzam się z twoją odpowiedzią. Na początku pospiesznie go przeczytałem i błędnie pomyślałem, że sugerujesz sekwencyjne wybieranie każdego elementu ze stałym prawdopodobieństwem k / n, co byłoby błędne - ale twoje podejście adaptacyjne wydaje mi się prawidłowe. Przepraszam za to.

Ok, a teraz dla kickera: asymptotycznie (dla ustalonego k, n rosnącego) jest n ^ k / k! wybory k elementów podzbioru z n elementów [jest to przybliżenie (n wybierz k)]. Jeśli n jest duże, a k nie jest bardzo małe, to te liczby są ogromne. Najlepsza długość cyklu, na jaką możesz liczyć w dowolnym standardowym 32-bitowym generatorze liczb losowych, to 2 ^ 32 = 256 ^ 4. Jeśli więc mamy listę 1000 elementów i chcemy losowo wybrać 5, nie ma mowy, żeby standardowy generator liczb losowych trafił we wszystkie możliwości. Jednakże, o ile nie przeszkadza Ci wybór, który działa dobrze dla mniejszych zestawów i zawsze „wygląda” losowo, to te algorytmy powinny działać.

Dodatek : Po napisaniu tego zdałem sobie sprawę, że trudno jest poprawnie wdrożyć pomysł (2), więc chciałem wyjaśnić tę odpowiedź. Aby uzyskać czas O (k log k), potrzebujesz struktury przypominającej tablicę, która obsługuje wyszukiwania i wstawianie O (log m) - może to zrobić zrównoważone drzewo binarne. Używając takiej struktury do zbudowania tablicy o nazwie s, oto kilka pseudopytonów:

# 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

Proponuję przejrzeć kilka przykładowych przypadków, aby zobaczyć, jak skutecznie implementuje to powyższe angielskie wyjaśnienie.

Myślę, że wybrana odpowiedź jest poprawna i całkiem słodka. Zaimplementowałem to jednak inaczej, ponieważ chciałem również uzyskać wynik w losowej kolejności.

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

Właśnie natknąłem się na ten problem, a dalsze wyszukiwanie w Google doprowadziło mnie do problemu losowego tasowania listy: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Aby całkowicie losowo potasować listę (w miejscu), wykonaj następujące czynności:

Aby przetasować tablicę a złożoną z n elementów (indeksy 0..n-1):

  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

Jeśli potrzebujesz tylko pierwszych 5 elementów, to zamiast uruchamiać i od n-1 do 1, wystarczy uruchomić go do n-5 (tj .: n-5)

Powiedzmy, że potrzebujesz k przedmiotów,

To staje się:

  for (i = n − 1; i >= n-k; i--)
  {
       j = random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]
  }

Każdy zaznaczony element jest zamieniany pod koniec tablicy, więc k wybranych elementów to ostatnie k elementów tablicy.

Zajmuje to czas O (k), gdzie k to liczba losowo wybranych elementów, których potrzebujesz.

Ponadto, jeśli nie chcesz modyfikować swojej początkowej listy, możesz zapisać wszystkie swoje zamiany na liście tymczasowej, odwrócić tę listę i zastosować je ponownie, wykonując w ten sposób odwrotny zestaw zamian i zwracając swoją początkową listę bez zmiany czas pracy O (k).

Wreszcie, dla prawdziwego sticklera, jeśli (n == k), powinieneś zatrzymać się na 1, a nie nk, ponieważ losowo wybrana liczba całkowita będzie zawsze wynosić 0.

Możesz z tego skorzystać, ale zamawianie będzie odbywać się po stronie klienta

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);

From Dragons in the Algorithm , interpretacja w 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--;
}

Algorytm ten wybierze unikalne wskazania listy pozycji.

Wybór N losowych przedmiotów z grupy nie powinien mieć nic wspólnego z porządkiem ! Losowość dotyczy nieprzewidywalności, a nie tasowania pozycji w grupie. Wszystkie odpowiedzi, które dotyczą jakiegoś rodzaju zamawiania, z pewnością będą mniej efektywne niż te, które tego nie robią. Ponieważ efektywność jest tutaj kluczowa, opublikuję coś, co nie zmienia zbytnio kolejności przedmiotów.

1) Jeśli potrzebujesz prawdziwie losowych wartości, co oznacza, że ​​nie ma ograniczeń co do elementów do wyboru (tj. Raz wybrany element można ponownie wybrać):

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

Jeśli wyłączysz flagę wyjątku, możesz wybierać losowe elementy dowolną liczbę razy.

Jeśli masz {1, 2, 3, 4}, to może dać {1, 4, 4}, {1, 4, 3} itd. Za 3 elementy lub nawet {1, 4, 3, 2, 4} za 5 sztuk!

Powinno to nastąpić dość szybko, ponieważ nie ma nic do sprawdzenia.

2) Jeśli potrzebujesz pojedynczych członków z grupy bez powtórzeń, skorzystam ze słownika (jak wielu już zauważyło).

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

Kod jest nieco dłuższy niż inne podejścia słownikowe, ponieważ nie tylko dodam, ale także usuwam z listy, więc jest to rodzaj dwóch pętli. Widać tutaj, że w ogóle niczego nie zmieniłem , gdy stanie countsię równy source.Count. To dlatego, że uważam, że losowość powinna występować w zwracanym zestawie jako całości . To znaczy, jeśli chcesz 5 losowych elementów z 1, 2, 3, 4, 5, nie powinno sprawa jeśli jego 1, 3, 4, 2, 5albo 1, 2, 3, 4, 5, ale jeśli potrzebujesz 4 pozycji z tego samego zestawu, to powinien w sposób nieprzewidywalny wydajność 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4itd. Po drugie, gdy liczba przypadkowych elementów, które należy zwrócona jest więcej niż połowa pierwotnej grupy, więc łatwiej ją usunąćsource.Count - countelementy z grupy niż dodawanie countelementów. Ze względu na wydajność użyłem sourcezamiast sourceDicttego losowego indeksu w metodzie usuwania.

Więc jeśli masz {1, 2, 3, 4}, może to skończyć się na {1, 2, 3}, {3, 4, 1} itd. Dla 3 elementów.

3) Jeśli potrzebujesz naprawdę odrębnych losowych wartości ze swojej grupy, biorąc pod uwagę duplikaty w oryginalnej grupie, możesz użyć tego samego podejścia, co powyżej, ale HashSetbędzie lżejsze niż słownik.

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

randomsZmienna skierowany jest HashSetdo uniknięcia duplikaty dodawano w najrzadszych najrzadszych przypadkach Random.Nextmogą wywoływać tę samą wartość, w szczególności, gdy listy wejście jest mała.

Więc {1, 2, 2, 4} => 3 losowe elementy => {1, 2, 4} i nigdy {1, 2, 2}

{1, 2, 2, 4} => 4 losowe przedmioty => wyjątek !! lub {1, 2, 4} w zależności od ustawionej flagi.

Niektóre z metod rozszerzających, których użyłem:

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

Jeśli chodzi o wydajność z dziesiątkami tysięcy pozycji na liście, które muszą być iterowane 10000 razy, możesz chcieć mieć szybszą klasę losową niż System.Random, ale nie sądzę, że to wielka sprawa, biorąc pod uwagę, że ta druga prawdopodobnie nigdy nie jest wąskie gardło, jest dość szybkie.

Edycja: Jeśli chcesz zmienić kolejność zwracanych produktów, nic nie może pokonać podejścia dhakima Fisher-Yates - krótkie, słodkie i proste.

Zastanawiałem się nad komentarzem @JohnShedletsky na temat zaakceptowanej odpowiedzi dotyczącej (parafraza):

powinieneś być w stanie to zrobić w O (subset.Length), a nie O (originalList.Length)

Zasadniczo powinieneś być w stanie wygenerować subsetlosowe indeksy, a następnie pobrać je z oryginalnej listy.

Metoda

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

}

Jeśli chcesz być jeszcze bardziej efektywny, prawdopodobnie używać HashSetz indeksami , a nie rzeczywiste elementy listy (w przypadku, gdy mamy złożonych typów lub kosztowne porównań);

Test jednostkowy

Aby upewnić się, że nie mamy żadnych kolizji itp.

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

Połączyłem kilka z powyższych odpowiedzi, aby utworzyć metodę rozszerzenia ocenianą leniwie. Moje testy wykazały, że podejście Kyle'a (Order (N)) jest wielokrotnie wolniejsze niż użycie zbioru przez drzausa do zaproponowania losowych wskaźników do wyboru (Order (K)). Pierwsza wykonuje o wiele więcej wywołań do generatora liczb losowych, a także wykonuje więcej iteracji po elementach.

Cele mojej realizacji to:

1) Nie uświadamiaj sobie pełnej listy, jeśli masz IEnumerable, który nie jest IList. Jeśli dostanę sekwencję miliardów pozycji, nie chcę, by zabrakło mi pamięci. Skorzystaj z podejścia Kyle'a, aby uzyskać rozwiązanie online.

2) Jeśli mogę stwierdzić, że jest to IList, użyj podejścia drzausa, z niespodzianką. Jeśli K to więcej niż połowa N, ryzykuję rzucanie się, ponieważ wielokrotnie wybieram wiele losowych wskaźników i muszę je pomijać. W ten sposób układam listę wskaźników, których NIE należy przechowywać.

3) Gwarantuję, że przedmioty zostaną zwrócone w tej samej kolejności, w jakiej zostały napotkane. Algorytm Kyle'a nie wymagał żadnych zmian. Algorytm drzausa wymagał, abym nie emitował przedmiotów w kolejności, w jakiej są wybrane wskaźniki losowe. Zbieram wszystkie indeksy w SortedSet, a następnie emituję elementy w posortowanej kolejności indeksów.

4) Jeśli K jest duże w porównaniu z N i odwracam sens zbioru, wówczas wyliczam wszystkie pozycje i sprawdzam, czy indeks nie znajduje się w zestawie. Oznacza to, że tracę czas działania Order (K), ale ponieważ K jest blisko N w tych przypadkach, nie tracę dużo.

Oto kod:

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

Używam wyspecjalizowanego generatora liczb losowych, ale jeśli chcesz, możesz po prostu użyć funkcji Random w języku C # . ( FastRandom został napisany przez Colina Greena i jest częścią SharpNEAT. Ma okres 2 ^ 128-1, czyli lepszy niż wiele RNG).

Oto testy jednostkowe:

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

Wychodząc od odpowiedzi @ ers, jeśli ktoś obawia się o możliwe różne implementacje OrderBy, powinno to być bezpieczne:

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

To najlepsze, co mogłem wymyślić przy pierwszym cięciu:

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

Używanie listy losowych w zakresie od 1 - całkowita liczba list, a następnie po prostu wyciąganie tych pozycji z listy wydawało się najlepszym sposobem, ale używanie Słownika w celu zapewnienia wyjątkowości jest czymś, nad czym wciąż się zastanawiam.

Zauważ również, że użyłem listy ciągów, w razie potrzeby zastąp.

Proste rozwiązanie, którego używam (prawdopodobnie nie jest dobre dla dużych list): Skopiuj listę do listy tymczasowej, a następnie w pętli losowo wybierz pozycję z listy tymczasowej i umieść ją na liście wybranych pozycji podczas usuwania z listy tymczasowej (więc nie może być wybrany ponownie).

Przykład:

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

Tutaj mamy jedną implementację opartą na tasowaniu Fishera-Yatesa, której złożoność algorytmu wynosi O (n), gdzie n jest podzbiorem lub rozmiarem próbki, a nie rozmiarem listy, jak wskazał John Shedletsky.

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

W oparciu o odpowiedź Kyle'a, oto moja implementacja C #.

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

Ta metoda może być równoważna z metodą Kyle'a.

Powiedzmy, że twoja lista ma rozmiar n i chcesz mieć k elementów.

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

Działa jak marzenie :)

-Alex Gilbert

czemu nie coś takiego:

 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#

Jest to o wiele trudniejsze niż mogłoby się wydawać. Zobacz wspaniały artykuł „Shuffling” autorstwa Jeffa.

Napisałem na ten temat bardzo krótki artykuł zawierający kod C #:
Zwróć losowy podzbiór N elementów z danej tablicy

Cel: Wybierz liczbę N elementów ze źródła kolekcji bez powielania. Stworzyłem rozszerzenie dla dowolnej kolekcji ogólnej. Oto jak to zrobiłem:

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

Niedawno zrobiłem to w moim projekcie, korzystając z pomysłu podobnego do punktu 1 Tylera .
Ładowałem kilka pytań i wybierałem pięć losowo. Sortowanie przeprowadzono za pomocą IComparer .
aWszystkie pytania zostały załadowane do listy QuestionSorter, która następnie została posortowana za pomocą funkcji Sortowanie listy i pierwszych k elementów, które zostały wybrane.

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

Stosowanie:

    List<QuestionSorter> unsortedQuestions = new List<QuestionSorter>();

    // add the questions here

    unsortedQuestions.Sort(unsortedQuestions as IComparer<QuestionSorter>);

    // select the first k elements

Oto moje podejście (pełny tekst tutaj http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

Powinien działać w O (K) zamiast O (N), gdzie K to liczba poszukiwanych elementów, a N to rozmiar listy do wyboru:

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

To nie jest tak eleganckie ani wydajne jak przyjęte rozwiązanie, ale można je szybko opisać. Najpierw losowo permutuj tablicę, a następnie wybierz pierwsze K elementów. W Pythonie

import numpy

N = 20
K = 5

idx = np.arange(N)
numpy.random.shuffle(idx)

print idx[:K]

Użyłbym metody rozszerzenia.

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

Pamięć: ~ liczba
Złożoność: O (liczba ² )

Gdy N jest bardzo duże, normalna metoda losowego tasowania liczb N i wybierania, powiedzmy, pierwszych k liczb, może być przeszkodą ze względu na złożoność przestrzeni. Poniższy algorytm wymaga tylko O ​​(k) zarówno dla złożoności czasowej, jak i przestrzennej.

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

Używanie LINQ z dużymi listami (gdy kosztowne jest dotknięcie każdego elementu) ORAZ jeśli możesz żyć z możliwością duplikatów:

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

Do mojego użytku miałem listę 100 000 elementów, a ponieważ były one wyciągane z bazy danych, skróciłem czas o połowę (lub lepiej) w porównaniu do rnd na całej liście.

Posiadanie dużej listy znacznie zmniejszy szanse na duplikaty.

To rozwiąże Twój problem

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