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

158

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

JC Grubbs
источник
12
Случайно, вы имеете в виду Inclusive или Exclusive? Можно ли выбрать один и тот же элемент более одного раза? (действительно случайно) Или, если элемент выбран, его уже нельзя выбрать из доступного пула?
Крендель

Ответы:

127

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

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

Кайл Кронин
источник
33
Я чувствую, что это не так. Кажется, что задний конец списка будет выбираться чаще, чем передний, так как задний конец будет видеть гораздо большие вероятности. Например, если первые 35 номеров не выбраны, последние 5 номеров должны быть выбраны. Первое число будет когда-либо видеть только 5/40 шанс, но это последнее число будет видеть 1/1 чаще, чем 5/40 раз. Вы должны будете рандомизировать список, прежде чем применять этот алгоритм.
Анкур Гоэль
23
Хорошо, я выполнил этот алгоритм 10 миллионов раз в списке из 40 элементов, каждый из которых имел выстрел 5/40 (.125) при выборе, а затем запустил эту симуляцию несколько раз. Оказывается, это распределяется неравномерно. Элементы с 16 по 22 выбраны недостаточно (16 = .123, 17 = .124), в то время как элемент 34 отобран (34 = .129). Элементы 39 и 40 также выбираются недостаточно, но не так сильно (39 = .1247, 40 = .1246)
Анкур Гоэль
22
@Ankur: я не верю, что это статистически значимо. Я считаю, что есть индуктивное доказательство того, что это обеспечит равномерное распределение.
рекурсивный
9
Я повторил одно и то же испытание 100 миллионов раз, и в моем испытании наименее выбранный элемент выбирался менее чем на 0,106% реже, чем наиболее часто выбранный элемент.
рекурсивный
5
@recursive: доказательство почти тривиально. Мы знаем, как выбрать K элементов из K для любого K и как выбрать 0 элементов из N для любого N. Предположим, что мы знаем метод для равномерного выбора K или K-1 элементов из N-1> = K; затем мы можем выбрать K элементов из N, выбрав первый элемент с вероятностью K / N, а затем, используя известный метод, выбрать все еще необходимые элементы K или K-1 из оставшегося N-1.
Ильмари Каронен
216

Используя linq:

YourList.OrderBy(x => rnd.Next()).Take(5)
Ers
источник
2
+1 Но если два элемента получают одинаковое число из rnd.Next () или аналогичного, то первый будет выбран, а второй, возможно, нет (если больше элементов не требуется). Тем не менее, он достаточно случайный в зависимости от использования.
Лассе Эспехолт
8
Я думаю, что порядок по O (n log (n)), поэтому я бы выбрал это решение, если основной проблемой является простота кода (то есть с небольшими списками).
Гвидо
2
Но разве это не перечисляет и не сортирует весь список? Если «быстрый», OP означает «легкий», а не «исполнитель» ...
drzaus
2
Это будет работать только в том случае, если OrderBy () вызывает ключ выбора только один раз для каждого элемента. Если он вызывает его всякий раз, когда хочет выполнить сравнение между двумя элементами, он каждый раз будет получать разное значение, что приведет к неправильной сортировке. В [документации] ( msdn.microsoft.com/en-us/library/vstudio/… ) не сказано, что это делает.
Оливер Бок
2
Остерегайтесь, если YourListесть много предметов, но вы хотите выбрать только несколько. В этом случае это не эффективный способ сделать это.
Каллум Уоткинс
39
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
    return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}
ваг
источник
27

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

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

(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

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

Тайлер
источник
2
для (1) вы можете перетасовать список быстрее, чем сортировка, для (2) вы будете смещать свой дистрибутив, используя%
jk.
Учитывая возражение, которое вы высказали в отношении длины цикла rng, есть ли способ, которым мы можем построить алгоритм, который будет выбирать все множества с равной вероятностью?
Иона
Для (1), чтобы улучшить O (n log (n)), вы можете использовать сортировку выбора, чтобы найти k наименьших элементов. Это будет работать в O (N * K).
Джаред
@Jonah: я так думаю. Давайте предположим, что мы можем объединить несколько независимых генераторов случайных чисел для создания большего ( crypto.stackexchange.com/a/27431 ). Тогда вам просто нужен достаточно большой диапазон, чтобы справиться с размером рассматриваемого списка.
Джаред
16

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

    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);
    }
Фрэнк Швитерман
источник
ЗДОРОВО! Действительно выручил меня!
Армстронгест
1
Есть ли у вас какие-либо причины не использовать новый метод Random (), основанный на Environment.TickCount или DateTime.Now.Millisecond?
Лассе Эспехолт
Нет, просто не знал, что по умолчанию существует.
Фрэнк Швитерман
2
Хорошо, год спустя, но ... Разве это не соответствует довольно короткому ответу @ ersin, и не потерпит ли он неудачу, если вы получите повторяющееся случайное число (где у Ersin будет отклонение по отношению к первому элементу повторяющейся пары)
Andiih
1
Random random = new Random(DateTime.Now.Millisecond);на каждый звонок однозначно неправильно. Создание нового экземпляра Randomкаждый раз уменьшает фактическую случайность. Используйте его static readonlyэкземпляр, желательно с конструктором по умолчанию.
jpmc26
12

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

dhakim
источник
Я реализовал это, используя C # в своем блоге: vijayt.com/post/random-select-using-fisher-yates-algorithm . Надеюсь, это поможет кому-то, ищущему путь C #.
Виджайст
9

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

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
Марван Рушди
источник
Согласовано. Это может быть не самым лучшим или самым случайным, но для подавляющего большинства людей этого будет достаточно.
Richiban
8

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

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

spoulson
источник
Только получить достаточно пункта в списке, но не получить случайно.
culithay
2
Эта реализация нарушена, потому что при использовании varрезультатов neededи availableоба являются целыми числами, что needed/availableвсегда дает 0.
Нико
1
Похоже, что это реализация принятого ответа.
DCShannon
6

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

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

Навфал
источник
6

Думал о комментарии @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);
        }
    }
}
drzaus
источник
2
Хорошая идея, с проблемами. (1) Если ваш большой список огромен (например, для чтения из базы данных), вы понимаете весь список, который может превышать объем памяти. (2) Если K близко к N, то вы будете очень много искать в невостребованном индексе в цикле, в результате чего коду потребуется непредсказуемое количество времени. Эти проблемы разрешимы.
Павел Чернох
1
Мое решение проблемы обмолота таково: если K <N / 2, сделайте это по-своему. Если K> = N / 2, выберите индексы, которые НЕ должны сохраняться, вместо тех, которые должны быть сохранены. Есть еще немного побеждать, но гораздо меньше.
Павел Чернох
Также заметил, что это изменяет порядок перечисляемых элементов, что может быть приемлемо в некоторых ситуациях, но не в других.
Павел Чернох
В среднем, для K = N / 2 (наихудший случай для предложенного Полом улучшения) алгоритм (улучшенный молот), по-видимому, принимает ~ 0,693 * N итераций. Теперь сделайте сравнение скорости. Это лучше, чем принятый ответ? Для каких размеров выборки?
mbomb007
6

Я объединил несколько из приведенных выше ответов, чтобы создать метод расширения 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));
    }
}
Павел Чернох
источник
Нет ли ошибки в тесте? У вас есть, if (itemsList != null && k < n/2)что означает внутри if invertSetвсегда, falseчто означает, что логика никогда не используется.
NetMage
4

Если исходить из ответа @ 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
hardsetting
источник
3

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

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

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

IanStallings
источник
1
Работал с первого выстрела!
Сангам
3

Простое решение, которое я использую (вероятно, не подходит для больших списков): скопируйте список во временный список, затем в цикле случайным образом выберите 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++;
 }
Тин М.
источник
Удаление из середины списка так часто будет дорогостоящим. Вы можете рассмотреть возможность использования связанного списка для алгоритма, требующего так много удалений. Или, что то же самое, замените удаленный элемент на нулевое значение, но тогда вы немного побьете, когда выберете уже удаленные элементы и вам придется выбирать снова.
Павел Чернох
3

Здесь у вас есть одна реализация, основанная на 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;
    }
}
Хесус Лопес
источник
2

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

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

Скажем, ваш список имеет размер 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--;
    }
} 

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

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

Алекс Гилберт
источник
1
Это выглядит эквивалентно мне. Сравните с аналогичным stackoverflow.com/a/48141/2449863
DCShannon
1

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

 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#
Кэмерон Эллис
источник
1

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

Я недавно сделал это в своем проекте, используя идею, похожую на точку 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
Hitec
источник
0

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

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

import numpy

N = 20
K = 5

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

print idx[:K]
apdnu
источник
0

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

    public static IEnumerable<T> TakeRandom<T>(this IEnumerable<T> elements, int countToTake)
    {
        var random = new Random();

        var internalList = elements.ToList();

        var selected = new List<T>();
        for (var i = 0; i < countToTake; ++i)
        {
            var next = random.Next(0, internalList.Count - selected.Count);
            selected.Add(internalList[next]);
            internalList[next] = internalList[internalList.Count - selected.Count];
        }
        return selected;
    }
Kvam
источник
0
public static IEnumerable<T> GetRandom<T>(this IList<T> list, int count, Random random)
    {
        // Probably you should throw exception if count > list.Count
        count = Math.Min(list.Count, count);

        var selectedIndices = new SortedSet<int>();

        // Random upper bound
        int randomMax = list.Count - 1;

        while (selectedIndices.Count < count)
        {
            int randomIndex = random.Next(0, randomMax);

            // skip over already selected indeces
            foreach (var selectedIndex in selectedIndices)
                if (selectedIndex <= randomIndex)
                    ++randomIndex;
                else
                    break;

            yield return list[randomIndex];

            selectedIndices.Add(randomIndex);
            --randomMax;
        }
    }

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

кардинальный
источник
0

Когда 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
Dai
источник
0

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

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

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

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

Wolf5
источник
Это решение может иметь повторяющиеся элементы! Случайного в списке дыр не может.
AxelWass
Хм. Правда. Где я использую это, это не имеет значения, хотя. Отредактировал ответ, чтобы отразить это.
Wolf5
-1

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

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]);
                }
Сирил
источник
Хотя это может ответить на вопрос, вы должны отредактировать свой ответ, чтобы включить объяснение того, как этот блок кода отвечает на вопрос. Это помогает обеспечить контекст и делает ваш ответ гораздо более полезным для будущих читателей.
прыгнул