Выберите N случайных элементов из списка <T> в C #

Мне нужен быстрый алгоритм, чтобы выбрать 5 случайных элементов из общего списка. Например, я хотел бы получить 5 случайных элементов из List<string>.

Итерируйте и для каждого элемента сделайте вероятность выбора = (необходимое число) / (оставшееся число)

Таким образом, если у вас было 40 предметов, у первого был бы шанс 5/40 быть выбранным. Если это так, у следующего есть шанс 4/39, в противном случае он имеет шанс 5/39. К тому времени, как вы доберетесь до конца, у вас будет 5 предметов, и часто вы будете иметь их все до этого.

Используя 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();
}

Это на самом деле более сложная проблема, чем кажется, в основном потому, что многие математически правильные решения не позволят вам использовать все возможности (подробнее об этом ниже).

Во-первых, вот несколько простых в реализации, корректных, если вы действительно имеете случайный номер генератора:

(0) ответ Кайла, который является O (n).

(1) Создайте список из n пар [(0, rand), (1, rand), (2, rand), ...], отсортируйте их по второй координате и используйте первые k (для вас k = 5) индексы, чтобы получить ваше случайное подмножество. Я думаю, что это легко реализовать, хотя это O (n log n) времени.

(2) Инициируйте пустой список s = [], который будет расти до индексов k случайных элементов. Случайно выберите число r в {0, 1, 2, ..., n-1}, r = rand% n и добавьте его к s. Затем возьмите r = rand% (n-1) и вставьте s; добавьте к r меньше элементов #, чем во s, чтобы избежать коллизий. Затем возьмите r = rand% (n-2) и делайте то же самое и т. Д., Пока у вас не будет k различных элементов в s. Это имеет наихудшее время выполнения O (k ^ 2). Так что для k << n это может быть быстрее. Если вы сохраняете сортировку и отслеживаете, какие у нее есть непрерывные интервалы, вы можете реализовать ее в O (k log k), но это больше работы.

@ Кайл - ты прав, если подумать, я согласен с твоим ответом. Сначала я поспешно прочитал его и по ошибке подумал, что вы указали на последовательный выбор каждого элемента с фиксированной вероятностью k / n, что было бы неправильно, но ваш адаптивный подход кажется мне правильным. Извини за это.

Хорошо, и теперь для кикера: асимптотически (для фиксированного k, n растет), есть n ^ k / k! выбор подмножества k элементов из n элементов [это приближение (n выбирать k)]. Если n велико, а k не очень мало, то эти числа огромны. Лучшая длина цикла, на которую вы можете рассчитывать в любом стандартном 32-битном генераторе случайных чисел, равна 2 ^ 32 = 256 ^ 4. Так что, если у нас есть список из 1000 элементов, и мы хотим выбрать 5 случайным образом, стандартный генератор случайных чисел не сможет использовать все возможности. Однако, если вы согласны с выбором, который отлично работает для небольших наборов и всегда «выглядит» случайным образом, эти алгоритмы должны быть в порядке.

Приложение : После написания этого я понял, что реализовать идею (2) сложно, поэтому я хотел уточнить этот ответ. Чтобы получить время O (k log k), вам нужна структура типа массива, которая поддерживает поиск и вставку O (log m) - сбалансированное двоичное дерево может это сделать. Используя такую ​​структуру для построения массива с именем s, вот несколько псевдопионов:

# 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

Я предлагаю пробежаться по нескольким примерам примеров, чтобы увидеть, как это эффективно реализует вышеприведенное объяснение на английском языке.

Я думаю, что выбранный ответ является правильным и довольно сладким. Я реализовал это по-другому, хотя, поскольку я также хотел результат в случайном порядке.

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

Я только столкнулся с этой проблемой, и некоторые другие поиски в Google привели меня к проблеме случайного перемешивания списка: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Чтобы полностью случайным образом перемешать ваш список (на месте), вы делаете это:

Чтобы перемешать массив a из n элементов (индексы 0..n-1):

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

Если вам нужны только первые 5 элементов, то вместо запуска i с n-1 до 1 вам нужно только запустить n-5 (то есть: n-5)

Допустим, вам нужно k предметов,

Это становится:

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

Каждый выбранный элемент меняется на конец массива, поэтому выбранные k элементов являются последними k элементами массива.

Это занимает время O (k), где k - количество случайно выбранных элементов, которые вам нужны.

Кроме того, если вы не хотите изменять свой первоначальный список, вы можете записать все свои свопы во временный список, отменить этот список и применить их снова, выполнив, таким образом, обратный набор свопов и вернув вам свой первоначальный список без изменения. время работы O (k).

Наконец, для реального кеша, если (n == k), вы должны остановиться на 1, а не на nk, так как случайно выбранное целое число всегда будет 0.

Вы можете использовать это, но заказ будет происходить на стороне клиента

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

От Драконов в Алгоритме , интерпретация в 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--;
}

Этот алгоритм будет выбирать уникальные признаки списка товаров.

Выбор N случайных элементов из группы не должен иметь ничего общего с порядком ! Случайность связана с непредсказуемостью, а не с перестановкой позиций в группе. Все ответы, связанные с каким-то порядком, обязательно будут менее эффективными, чем те, которые этого не делают. Поскольку эффективность является ключевым моментом здесь, я опубликую то, что не слишком меняет порядок элементов.

1) Если вам нужны истинные случайные значения, что означает, что нет никаких ограничений на выбор элементов (т. Е. Один раз выбранный элемент может быть повторно выбран):

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

Если вы установили флаг исключения, то вы можете выбирать случайные элементы любое количество раз.

Если у вас есть {1, 2, 3, 4}, то он может дать {1, 4, 4}, {1, 4, 3} и т. Д. Для 3 предметов или даже {1, 4, 3, 2, 4} для 5 штук!

Это должно быть довольно быстро, так как проверять нечего.

2) Если вам нужны отдельные участники из группы без повторов, то я бы положился на словарь (как уже отмечали многие).

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

Код немного длиннее, чем другие словарные подходы, потому что я не только добавляю, но и удаляю из списка, так что это своего рода два цикла. Здесь вы можете видеть, что я вообще ничего не переупорядочивал , когда countстановился равным source.Count. Это потому, что я считаю, что случайность должна быть в возвращаемом множестве в целом . Я имею в виду , если вы хотите 5 случайных элементов из 1, 2, 3, 4, 5, он должен не имеет значения , если его 1, 3, 4, 2, 5или 1, 2, 3, 4, 5, но если вам нужно 4 элементов из того же набора, то он должен непредсказуемо выхода в 1, 2, 3, 4, 1, 3, 5, 2,2, 3, 5, 4 и т.д. Во- вторых, когда подсчет случайных предметов, подлежащих возвращается более половины исходной группы, тогда ее легче удалитьsource.Count - countэлементы из группы, чем добавление countэлементов. Из соображений производительности я использовал sourceвместо того,sourceDict чтобы затем получить случайный индекс в методе удаления.

Так что если у вас есть {1, 2, 3, 4}, это может закончиться в {1, 2, 3}, {3, 4, 1} и т. Д. Для 3 элементов.

3) Если вам нужны действительно отличные случайные значения от вашей группы с учетом дубликатов в исходной группе, то вы можете использовать тот же подход, что и выше, но HashSetон будет легче словаря.

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

randomsПеременной принято , HashSetчтобы избежать дубликатов добавляют в редчайших редких случаях , когда Random.Nextможет дать такое же значение, особенно когда список входных мал.

Итак, {1, 2, 2, 4} => 3 случайных элемента => {1, 2, 4} и никогда {1, 2, 2}

{1, 2, 2, 4} => 4 случайных элемента => исключение !! или {1, 2, 4} в зависимости от установленного флага.

Некоторые из методов расширения, которые я использовал:

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

Если все дело в производительности с десятками тысяч элементов в списке, которые нужно повторять 10000 раз, то вам может потребоваться более быстрый случайный класс, чем System.Random, но я не думаю, что это большая проблема, учитывая, что последний, скорее всего, никогда не будет узкое место, достаточно быстро ..

Редактировать: Если вам нужно изменить порядок возвращаемых предметов, то нет ничего, что могло бы превзойти подход Дхакима Фишера-Йейтса - короткий, приятный и простой.

Думал о комментарии @JohnShedletsky на принятый ответ относительно (перефразировать):

Вы должны быть в состоянии сделать это в O (subset.Length), а не в O (originalList.Length)

По сути, вы должны быть в состоянии генерировать subset случайные индексы, а затем вынимать их из исходного списка.

Метод

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

}

Если вы хотите быть еще более эффективным, вы, вероятно, использовали бы один HashSetиз показателей , а не фактические элементы списка (в случае, если у вас есть сложные типы или дорогостоящие сравнения);

Модульный тест

И чтобы убедиться, что у нас нет столкновений и т. Д.

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

Я объединил несколько из приведенных выше ответов, чтобы создать метод расширения Lazily. Мои тесты показали, что подход Кайла (Order (N)) во много раз медленнее, чем использование drzaus набора для предложения случайных индексов на выбор (Order (K)). Первый выполняет гораздо больше обращений к генератору случайных чисел, а также выполняет итерации по элементам.

Целями моей реализации были:

1) Не реализовывать полный список, если дан IEnumerable, который не является IList. Если мне дают последовательность из миллиарда предметов, я не хочу исчерпывать память. Используйте подход Кайла для решения онлайн.

2) Если я могу сказать, что это IList, используйте подход drzaus с изюминкой. Если K больше половины N, я рискую побеждать, так как снова и снова выбираю много случайных индексов и вынужден их пропустить. Таким образом я составляю список индексов, которые НЕ сохраняются.

3) Я гарантирую, что предметы будут возвращены в том же порядке, в котором они были обнаружены. Алгоритм Кайла не требует изменений. Алгоритм дрзауса требовал, чтобы я не генерировал элементы в порядке выбора случайных индексов. Я собираю все индексы в SortedSet, а затем отправляю элементы в порядке отсортированных индексов.

4) Если K больше, чем N, и я инвертирую смысл набора, я перечисляю все элементы и проверяю, не находится ли индекс в наборе. Это означает, что я теряю время выполнения Order (K), но поскольку в этих случаях K близко к N, я не теряю много.

Вот код:

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

Я использую специализированный генератор случайных чисел, но вы можете просто использовать C # Random, если хотите. ( FastRandom был написан Колином Грином и является частью SharpNEAT. Он имеет период 2 ^ 128-1, что лучше, чем у многих ГСЧ.)

Вот модульные тесты:

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

Если исходить из ответа @ ers, если вы беспокоитесь о возможных различных реализациях OrderBy, это должно быть безопасно:

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

Это лучшее, что я мог придумать для первого среза:

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

Использование списка случайных чисел в диапазоне от 1 до общего числа списков, а затем просто извлечение этих элементов из списка, казалось бы, лучшим способом, но использование словаря для обеспечения уникальности - это то, над чем я все еще размышляю.

Также обратите внимание, что я использовал список строк, замените при необходимости.

Простое решение, которое я использую (вероятно, не подходит для больших списков): скопируйте список во временный список, затем в цикле случайным образом выберите Item из временного списка и поместите его в список выбранных элементов, удаляя его из временного списка (так что это не может быть перевыбранный).

Пример:

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

Здесь у вас есть одна реализация, основанная на Shuffle Фишера-Йейтса, чья сложность алгоритма O (n), где n - размер подмножества или выборки, а не размер списка, как указал Джон Шедлецкий.

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

Основываясь на ответе Кайла, вот моя реализация на 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 ;
}

Этот метод может быть эквивалентен методу Кайла.

Скажем, ваш список имеет размер n и вы хотите k элементов.

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

Работает как шарм :)

Алекс Гилберт

почему не как то так

 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#

Это намного сложнее, чем можно подумать. Смотрите отличную статью "Перемешивание" от Джеффа.

Я написал очень короткую статью на эту тему, включая код C #:
возвращать случайное подмножество из N элементов данного массива

Цель: выбрать N количество элементов из источника коллекции без дублирования. Я создал расширение для любой общей коллекции. Вот как я это сделал:

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

Я недавно сделал это в своем проекте, используя идею, похожую на точку 1 Тайлера .
Я загружал кучу вопросов и выбирал пять наугад. Сортировка была достигнута с использованием IComparer .
Все вопросы были загружены в список QuestionSorter, который затем сортировался с использованием функции сортировки списка и первых k элементов, которые были выбраны.

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

Использование:

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

    // add the questions here

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

    // select the first k elements

Вот мой подход (полный текст здесь http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

Он должен работать в O (K) вместо O (N), где K - количество искомых элементов, а N - размер списка на выбор:

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

Это не так элегантно или эффективно, как принятое решение, но его быстро написать. Сначала перестановите массив случайным образом, затем выберите первые K элементов. В питоне

import numpy

N = 20
K = 5

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

print idx[:K]

Я бы использовал метод расширения.

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

Память: ~
Сложность: O (количество ² )

Когда N очень большое, обычный метод, который случайным образом перемешивает N чисел и выбирает, скажем, первые k чисел, может быть запрещающим из-за сложности пространства. Следующий алгоритм требует только O (k) для сложности времени и пространства.

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

Использование LINQ с большими списками (когда дорого касаться каждого элемента) И если вы можете жить с возможностью дублирования:

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

Для моего использования у меня был список из 100 000 элементов, и из-за их извлечения из БД я потратил примерно вдвое (или лучше) время по сравнению с rnd во всем списке.

Наличие большого списка значительно сократит шансы на дубликаты.

Это решит вашу проблему

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