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

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

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

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

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

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

(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

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

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

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 до общего количества списка, а затем простое извлечение этих элементов в списке казалось лучшим способом, но использование словаря для обеспечения уникальности - это то, над чем я все еще обдумываю.

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

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

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

Недавно я сделал это в своем проекте, используя идею, похожую на Пункт 1 Тайлера.
. Я загружал кучу вопросов и выбирал пять наугад. Сортировка производилась с помощью IComparer.
. aВсе вопросы были загружены в список 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

почему бы не что-то вроде этого:

 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#

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

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

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

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

Используя linq:

YourList.OrderBy(x => rnd.Next()).Take(5)

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

Пример:

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

Вот мой подход (полный текст здесь 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;
}

Я только что столкнулся с этой проблемой, и еще один поиск в 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).

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

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

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

public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
    return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}

Выбор 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;
}

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

If you have { 1, 2, 3, 4 }, then it can give { 1, 4, 4 }, { 1, 4, 3 } etc for 3 items or even { 1, 4, 3, 2, 4 } for 5 items!

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

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, чтобы получить случайный индекс в методе удаления.

So if you have { 1, 2, 3, 4 }, this can end up in { 1, 2, 3 }, { 3, 4, 1 } etc for 3 items.

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 может давать одно и то же значение, особенно когда список ввода небольшой.

So { 1, 2, 2, 4 } => 3 random items => { 1, 2, 4 } and never { 1, 2, 2}

{ 1, 2, 2, 4 } => 4 random items => exception!! or { 1, 2, 4 } depending on the flag set.

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

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, но я не думаю, что это большое дело, учитывая, что последнее, скорее всего, никогда не будет узким местом , довольно быстро ..

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

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

import numpy

N = 20
K = 5

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

print idx[:K]

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

you should be able to to this in O(subset.Length), rather than 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);
        }
    }
}

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

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

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

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

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

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

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

3) Я гарантирую, что товары будут возвращены в том же порядке, в котором они были обнаружены. Алгоритм Кайла не требовал изменений. Алгоритм drzaus требовал, чтобы я не выделял элементы в том порядке, в котором выбираются случайные индексы. Я собираю все индексы в 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# Случайный, если хотите. (FastRandom был написан Колином Грином и является частью SharpNEAT. Он имеет период 2 ^ 128-1, что лучше, чем у многих RNG.)

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

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

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

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

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

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

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

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

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

Память: ~ count
Сложность: O (count²)

Когда 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

Здесь у вас есть одна реализация, основанная на Фишер-Йейтс в случайном порядке, сложность алгоритма которой равна 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;
    }
}

Исходя из ответа @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

Цель: выбрать количество 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;
    }
}

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

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

Спустя 12 лет, и этот вопрос все еще активен, я не нашел реализации решения Кайла, которое мне понравилось, поэтому вот оно:

public IEnumerable<T> TakeRandom<T>(IEnumerable<T> collection, int take)
{
    var random = new Random();
    var available = collection.Count();
    var needed = take;
    foreach (var item in collection)
    {
        if (random.Next(available) < needed)
        {
            needed--;
            yield return item;
            if (needed == 0)
            {
                break;
            }
        }
        available--;
    }
}

Вот эталон трех разных методов:

1. Реализация принятого ответа от Кайл.
2. Подход, основанный на случайном выборе индекса с фильтрацией дублирования HashSet, из Drzaus.
3. Более академический подход, опубликованный Хесус Лопес, называется Фишер – Йетс в случайном порядке.

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

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

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

Как ни странно, эта проблема временной сложности O(n) верна, даже если вы касаетесь списка только тогда, когда действительно возвращаете элемент, как я это делаю в своей реализации. Единственное, что я могу сказать, это то, что Random.Next() довольно медленный, и производительность улучшается, если вы генерируете только одно случайное число для каждого выбранного элемента.

И, что также интересно, стандартное отклонение решения Кайла было значительно выше в сравнении. Я понятия не имею, почему; возможно виновата моя реализация.

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

static void Main()
{
    BenchmarkRunner.Run<Benchmarks>();

    new Benchmarks() { ListSize = 100, SelectionSize = 10 }
        .BenchmarkStdDev();
}

[MemoryDiagnoser]
public class Benchmarks
{
    [Params(50, 500, 5000)]
    public int ListSize;

    [Params(5, 10, 25, 50)]
    public int SelectionSize;

    private Random _rnd;
    private List<int> _list;
    private int[] _hits;

    [GlobalSetup]
    public void Setup()
    {
        _rnd = new Random(12345);
        _list = Enumerable.Range(0, ListSize).ToList();
        _hits = new int[ListSize];
    }

    [Benchmark]
    public void Test_IterateSelect()
        => Random_IterateSelect(_list, SelectionSize).ToList();

    [Benchmark]
    public void Test_RandomIndices() 
        => Random_RandomIdices(_list, SelectionSize).ToList();

    [Benchmark]
    public void Test_FisherYates() 
        => Random_FisherYates(_list, SelectionSize).ToList();

    public void BenchmarkStdDev()
    {
        RunOnce(Random_IterateSelect, "IterateSelect");
        RunOnce(Random_RandomIdices, "RandomIndices");
        RunOnce(Random_FisherYates, "FisherYates");

        void RunOnce(Func<IEnumerable<int>, int, IEnumerable<int>> method, string methodName)
        {
            Setup();
            for (int i = 0; i < 1000000; i++)
            {
                var selected = method(_list, SelectionSize).ToList();
                Debug.Assert(selected.Count() == SelectionSize);
                foreach (var item in selected) _hits[item]++;
            }
            var stdDev = GetStdDev(_hits);
            Console.WriteLine($"StdDev of {methodName}: {stdDev :n} (% of average: {stdDev / (_hits.Average() / 100) :n})");
        }

        double GetStdDev(IEnumerable<int> hits)
        {
            var average = hits.Average();
            return Math.Sqrt(hits.Average(v => Math.Pow(v - average, 2)));
        }
    }

    public IEnumerable<T> Random_IterateSelect<T>(IEnumerable<T> collection, int needed)
    {
        var count = collection.Count();
        for (int i = 0; i < count; i++)
        {
            if (_rnd.Next(count - i) < needed)
            {
                yield return collection.ElementAt(i);
                if (--needed == 0)
                    yield break;
            }
        }
    }

    public IEnumerable<T> Random_RandomIdices<T>(IEnumerable<T> list, int needed)
    {
        var selectedItems = new HashSet<T>();
        var count = list.Count();

        while (needed > 0)
            if (selectedItems.Add(list.ElementAt(_rnd.Next(count))))
                needed--;

        return selectedItems;
    }

    public IEnumerable<T> Random_FisherYates<T>(IEnumerable<T> list, int sampleSize)
    {
        var count = list.Count();
        if (sampleSize > count) throw new ArgumentException("sampleSize may not be greater than list count", "sampleSize");
        var indices = new Dictionary<int, int>(); int index;

        for (int i = 0; i < sampleSize; i++)
        {
            int j = _rnd.Next(i, count);
            if (!indices.TryGetValue(j, out index)) index = j;

            yield return list.ElementAt(index);

            if (!indices.TryGetValue(i, out index)) index = i;
            indices[j] = index;
        }
    }
}

Выход:

|        Method | ListSize | Select |        Mean |     Error |    StdDev |  Gen 0 | Allocated |
|-------------- |--------- |------- |------------:|----------:|----------:|-------:|----------:|
| IterateSelect |       50 |      5 |    711.5 ns |   5.19 ns |   4.85 ns | 0.0305 |     144 B |
| RandomIndices |       50 |      5 |    341.1 ns |   4.48 ns |   4.19 ns | 0.0644 |     304 B |
|   FisherYates |       50 |      5 |    573.5 ns |   6.12 ns |   5.72 ns | 0.0944 |     447 B |

| IterateSelect |       50 |     10 |    967.2 ns |   4.64 ns |   3.87 ns | 0.0458 |     220 B |
| RandomIndices |       50 |     10 |    709.9 ns |  11.27 ns |   9.99 ns | 0.1307 |     621 B |
|   FisherYates |       50 |     10 |  1,204.4 ns |  10.63 ns |   9.94 ns | 0.1850 |     875 B |

| IterateSelect |       50 |     25 |  1,358.5 ns |   7.97 ns |   6.65 ns | 0.0763 |     361 B |
| RandomIndices |       50 |     25 |  1,958.1 ns |  15.69 ns |  13.91 ns | 0.2747 |    1298 B |
|   FisherYates |       50 |     25 |  2,878.9 ns |  31.42 ns |  29.39 ns | 0.3471 |    1653 B |

| IterateSelect |       50 |     50 |  1,739.1 ns |  15.86 ns |  14.06 ns | 0.1316 |     629 B |
| RandomIndices |       50 |     50 |  8,906.1 ns |  88.92 ns |  74.25 ns | 0.5951 |    2848 B |
|   FisherYates |       50 |     50 |  4,899.9 ns |  38.10 ns |  33.78 ns | 0.4349 |    2063 B |

| IterateSelect |      500 |      5 |  4,775.3 ns |  46.96 ns |  41.63 ns | 0.0305 |     144 B |
| RandomIndices |      500 |      5 |    327.8 ns |   2.82 ns |   2.50 ns | 0.0644 |     304 B |
|   FisherYates |      500 |      5 |    558.5 ns |   7.95 ns |   7.44 ns | 0.0944 |     449 B |

| IterateSelect |      500 |     10 |  5,387.1 ns |  44.57 ns |  41.69 ns | 0.0458 |     220 B |
| RandomIndices |      500 |     10 |    648.0 ns |   9.12 ns |   8.54 ns | 0.1307 |     621 B |
|   FisherYates |      500 |     10 |  1,154.6 ns |  13.66 ns |  12.78 ns | 0.1869 |     889 B |

| IterateSelect |      500 |     25 |  6,442.3 ns |  48.90 ns |  40.83 ns | 0.0763 |     361 B |
| RandomIndices |      500 |     25 |  1,569.6 ns |  15.79 ns |  14.77 ns | 0.2747 |    1298 B |
|   FisherYates |      500 |     25 |  2,726.1 ns |  25.32 ns |  22.44 ns | 0.3777 |    1795 B |

| IterateSelect |      500 |     50 |  7,775.4 ns |  35.47 ns |  31.45 ns | 0.1221 |     629 B |
| RandomIndices |      500 |     50 |  2,976.9 ns |  27.11 ns |  24.03 ns | 0.6027 |    2848 B |
|   FisherYates |      500 |     50 |  5,383.2 ns |  36.49 ns |  32.35 ns | 0.8163 |    3870 B |

| IterateSelect |     5000 |      5 | 45,208.6 ns | 459.92 ns | 430.21 ns |      - |     144 B |
| RandomIndices |     5000 |      5 |    328.7 ns |   5.15 ns |   4.81 ns | 0.0644 |     304 B |
|   FisherYates |     5000 |      5 |    556.1 ns |  10.75 ns |  10.05 ns | 0.0944 |     449 B |

| IterateSelect |     5000 |     10 | 49,253.9 ns | 420.26 ns | 393.11 ns |      - |     220 B |
| RandomIndices |     5000 |     10 |    642.9 ns |   4.95 ns |   4.13 ns | 0.1307 |     621 B |
|   FisherYates |     5000 |     10 |  1,141.9 ns |  12.81 ns |  11.98 ns | 0.1869 |     889 B |

| IterateSelect |     5000 |     25 | 54,044.4 ns | 208.92 ns | 174.46 ns | 0.0610 |     361 B |
| RandomIndices |     5000 |     25 |  1,480.5 ns |  11.56 ns |  10.81 ns | 0.2747 |    1298 B |
|   FisherYates |     5000 |     25 |  2,713.9 ns |  27.31 ns |  24.21 ns | 0.3777 |    1795 B |

| IterateSelect |     5000 |     50 | 54,418.2 ns | 329.62 ns | 308.32 ns | 0.1221 |     629 B |
| RandomIndices |     5000 |     50 |  2,886.4 ns |  36.53 ns |  34.17 ns | 0.6027 |    2848 B |
|   FisherYates |     5000 |     50 |  5,347.2 ns |  59.45 ns |  55.61 ns | 0.8163 |    3870 B |

StdDev of IterateSelect: 671.88 (% of average: 0.67)
StdDev of RandomIndices: 296.07 (% of average: 0.30)
StdDev of FisherYates: 280.47 (% of average: 0.28)