algorithm for selecting N random elements from a List in C#

Question

I need a quick algorithm to select 4 random elements from a generic list. For example, I'd like to get 4 random elements from a List and then based on some calculations if elements found not valid then it should again select next 4 random elements from the list.

Answer 1

You can store indexes in some list to get non-repeated indexes:

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

Then you can do some calculation and call this method:

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

Answer 2

something like that:

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 3

You could do it like this

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

Then use the extension method like this:

    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 4

Suppose that the length of the List is N. Now suppose that you will put these 4 numbers in another List called out. Then you can loop through the List and the probability of the element you are on being chosen is

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

Answer 5

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
)

This is the pseudo code, but i think you should of come up with this yourself. Hope it helps:)

Answer 6

All the answers up to now have one fundamental flaw; you are asking for an algorithm that will generate a random combination of n elements and this combination, following some logic rules, will be valid or not. If its not, a new combination should be produced. Obviously, this new combination should be one that has never been produced before. All the proposed algorithms do not enforce this. If for example out of 1000000 possible combinations, only one is valid, you might waste a whole lot of resources until that particular unique combination is produced.

So, how to solve this? Well, the answer is simple, create all possible unique solutions, and then simply produce them in a random order. Caveat: I will suppose that the input stream has no repeating elements, if it does, then some combinations will not be unique.

First of all, lets write ourselves a handy immutable stack:

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

This will make our life easier while producing all combinations by recursion. Next, let's get the signature of our main method right:

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

Ok, that looks about right. Now let's implement this thing:

    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, all we are doing here is producing random indexees, checking we haven't produced it yet (we use a HashSet<int> for this), and returning the combination at that index.

Simple, now we only need to take care of GetAllPossibleCombinations(data, combinationLength).

Thats easy, we'll use recursion. Our bail out condition is when our current combination is the specified length. Another caveat: I'm omitting argument validation throughout the whole code, things like checking for null or if the specified length is not bigger than the input length, etc. should be taken care of.

Just for the fun, I'll be using some minor C#7 syntax here: nested functions.

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

And there we go, now we can use this:

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

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

And sure enough, the output is:

bc
cb
ab
ac
ba
ca