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

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

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

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

Используя список randoms в диапазоне 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--;
}

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

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

Первый, вот некоторые легкие к реализации, correct-if-you-have-a-truly-random-number генератор:

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

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

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

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

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

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

# 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

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

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

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