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

Question

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

Answer 1

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

(4 - (out.Count))/(N - currentIndex) 

Answer 2

Вы можете хранить индексы в некотором списке, чтобы получить неповторяющиеся индексы:

List<T> GetRandomElements<T>(List<T> allElements, int randomCount = 4) 
{ 
    if (allElements.Count < randomCount) 
    { 
     return allElements; 
    } 

    List<int> indexes = new List<int>(); 

    // use HashSet if performance is very critical and you need a lot of indexes 
    //HashSet<int> indexes = new HashSet<int>(); 

    List<T> elements = new List<T>(); 

    Random random = new Random(); 
    while (indexes.Count < randomCount) 
    { 
     int index = random.Next(allElements.Count); 
     if (!indexes.Contains(index)) 
     { 
      indexes.Add(index); 
      elements.Add(allElements[index]); 
     } 
    } 

    return elements; 
} 

Тогда вы можете сделать некоторые расчеты и вызывать этот метод:

void Main(String[] args) 
{ 
    do 
    { 
     List<int> elements = GetRandomelements(yourElements); 
     //do some calculations 
    } while (some condition); // while result is not right 
} 

Answer 3

что-то вроде этого:

using System; 
using System.Collections.Generic; 

     public class Program 
     { 
      public static void Main() 
      { 
       var list = new List<int>(); 

       list.Add(1); 
       list.Add(2); 
       list.Add(3); 
       list.Add(4); 
       list.Add(5); 

       int n = 4; 

       var rand = new Random(); 

       var randomObjects = new List<int>(); 

       for (int i = 0; i<n; i++) 
       { 
        var index = rand.Next(list.Count); 

        randomObjects.Add(list[index]); 
       }  

      } 
     } 

Answer 4

funcion (list) 
(
loop i=0 i < 4 
    index = (int) length(list)*random(0 -> 1) 
    element[i] = list[index] 
return element 
) 

while(check == false) 
(
    elements = funcion (list) 

    Do some calculation which returns check == false /true 
) 

Это псевдокод, но я думаю, вы должны придумать это сами. Надеюсь, что это помогает :)

Answer 5

Вы можете сделать это, как этот

public static class Extensions 
    { 
     public static Dictionary<int, T> GetRandomElements<T>(this IList<T> list, int quantity) 
     { 
      var result = new Dictionary<int, T>(); 
      if (list == null) 
       return result; 
      Random rnd = new Random(DateTime.Now.Millisecond); 
      for (int i = 0; i < quantity; i++) 
      { 
       int idx = rnd.Next(0, list.Count); 
       result.Add(idx, list[idx]); 
      } 
      return result; 
     } 
    } 

Затем с помощью метода расширения, как это:

List<string> list = new List<string>() { "a", "b", "c", "d", "e", "f", "g", "h" }; 
    Dictionary<int, string> randomElements = list.GetRandomElements(3); 
    foreach (KeyValuePair<int, string> elem in randomElements) 
    { 
     Console.WriteLine($"index in original list: {elem.Key} value: {elem.Value}"); 
    } 

Answer 6

Все ответы до сих пор имеют один существенный недостаток; вы запрашиваете алгоритм, который будет генерировать случайную комбинацию из n элементов, и эта комбинация, следуя некоторым логическим правилам, будет действительна или нет. Если это не так, следует создать новую комбинацию. Очевидно, эта новая комбинация должна быть такой, которая никогда не производилась раньше. Все предлагаемые алгоритмы не обеспечивают этого. Если, например, из 1000000 возможных комбинаций, действителен только один, вы можете потратить массу ресурсов до тех пор, пока не будет создана эта уникальная комбинация.

Итак, как это решить? Ну, ответ прост, создайте все возможные уникальные решения, а затем просто производите их в произвольном порядке. Предостережение. Предположим, что входной поток не имеет повторяющихся элементов, если это так, то некоторые комбинации не будут уникальными.

Прежде всего, давайте напишем себе удобный непреложный стек:

class ImmutableStack<T> : IEnumerable<T> 
{ 
    public static readonly ImmutableStack<T> Empty = new ImmutableStack<T>(); 
    private readonly T head; 
    private readonly ImmutableStack<T> tail; 
    public int Count { get; } 

    private ImmutableStack() 
    { 
     Count = 0; 
    } 

    private ImmutableStack(T head, ImmutableStack<T> tail) 
    { 
     this.head = head; 
     this.tail = tail; 
     Count = tail.Count + 1; 
    } 

    public T Peek() 
    { 
     if (this == Empty) 
      throw new InvalidOperationException("Can not peek a empty stack."); 

     return head; 
    } 

    public ImmutableStack<T> Pop() 
    { 
     if (this == Empty) 
      throw new InvalidOperationException("Can not pop a empty stack."); 

     return tail; 
    } 

    public ImmutableStack<T> Push(T item) => new ImmutableStack<T>(item, this); 

    public IEnumerator<T> GetEnumerator() 
    { 
     var current = this; 

     while (current != Empty) 
     { 
      yield return current.head; 
      current = current.tail; 
     } 
    } 

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); 
} 

Это сделает нашу жизнь проще, производя все комбинации рекурсией. Затем давайте получим подпись нашего основного метода:

public static IEnumerable<IEnumerable<T>> GetAllPossibleCombinationsInRandomOrder<T>(
    IEnumerable<T> data, int combinationLength) 

Хорошо, это выглядит правильно. Теперь давайте реализуем эту вещь:

var allCombinations = GetAllPossibleCombinations(data, combinationLength).ToArray(); 
    var rnd = new Random(); 
    var producedIndexes = new HashSet<int>(); 

    while (producedIndexes.Count < allCombinations.Length) 
    { 
     while (true) 
     { 
      var index = rnd.Next(allCombinations.Length); 

      if (!producedIndexes.Contains(index)) 
      { 
       producedIndexes.Add(index); 
       yield return allCombinations[index]; 
       break; 
      } 
     } 
    } 

Ok, все, что мы делаем здесь, производит случайные indexees, проверяя, мы не дали его пока (мы используем HashSet<int> для этого), и возвращает комбинацию по этому индексу.

Простой, теперь нам нужно только позаботиться о GetAllPossibleCombinations(data, combinationLength).

Это легко, мы будем использовать рекурсию. Условие нашего спасения - это когда наша текущая комбинация является указанной длиной. Еще одна оговорка: я пропустил проверку аргументов на всем протяжении кода, например, проверка на null или если указанная длина не больше длины ввода и т. Д., То вам следует позаботиться.

Просто для удовольствия, я буду использовать небольшой синтаксис C# 7 здесь: вложенные функции.

public static IEnumerable<IEnumerable<T>> GetAllPossibleCombinations<T>(
    IEnumerable<T> stream, int length) 
{ 
    return getAllCombinations(stream, ImmutableStack<T>.Empty); 

    IEnumerable<IEnumerable<T>> getAllCombinations<T>(IEnumerable<T> currentData, ImmutableStack<T> combination) 
    { 
     if (combination.Count == length) 
      yield return combination; 

     foreach (var d in currentData) 
     { 
      var newCombination = combination.Push(d); 

      foreach (var c in getAllCombinations(currentData.Except(new[] { d }), newCombination)) 
      { 
       yield return c; 
      } 
     } 
    } 
} 

И мы идем, теперь мы можем использовать это:

var data = "abc"; 
var random = GetAllPossibleCombinationsInRandomOrder(data, 2); 

foreach (var r in random) 
{ 
    Console.WriteLine(string.Join("", r)); 
} 

И, конечно, выход:

bc 
cb 
ab 
ac 
ba 
ca