Description
This is a utility algorithm that selects a number of elements from a source list without repeating elements.
Background
My use case is creating a random path for a NPC that has to investigate a zone (polygon) containing predetermined interest points. Different effects are triggered upon reaching a point: achieving a certain heading, playing an animation, etc. Thus, a simple simulation of a random NPC routine can be achieved.
Requirements
- Select \$n\$ random elements from a
IList<T>without repeating any elements where \$n <= list.Count\$. Multiple calls to this operation can be made from different parts of the program without repeating the elements until all elements have been used exactly once. - Select \$n\$ random elements from a
IList<T>without repeating any elements until all elements have been selected at least once. As above while taking into consideration that elements can appear more than once only if all elements have been selected previously an equal number of times.
Implementation
Note 1: Namespaces are omitted.
Note 2: Limited to C# .Net Framework 4.5.2
Thought
Selecting random elements from a list is equivalent to selecting random indices followed by extracting the elements based on the selected random sequence of indices. The indices must be randomly selected without repetition. Therefore, I create a class to shuffle around indices:
IndexShuffler.cs
public class IndexShuffler
{
private static Random random = new Random();
private int[] indices;
private int remaining;
/// <summary>
/// Create an instance with the specified number of indices.
/// </summary>
/// <param name="size">The number of indices to generate (inclusive).</param>
public IndexShuffler(int size)
{
indices = new int[size];
remaining = size;
// did not use Enumerable.Range() to avoid having a call to ToArray()
for (int i = 0; i < size; ++i)
{
indices[i] = i;
}
}
/// <summary>
/// Shuffles one value from the index list to a random spot in the index list.
/// The selected value will not be reshuffled in further iterations until all
/// other values in the index list are shuffled.
/// </summary>
/// <param name="n">The number of shuffle iterations.</param>
public void Shuffle(int n)
{
while (n-- > 0)
{
Swap(random.Next(remaining--), remaining);
}
}
/// <summary>
/// Shuffles the contained indices once and returns the selected index of the shuffle.
/// </summary>
/// <returns>The selected index of the shuffle.</returns>
public int ShuffleWrap()
{
if (remaining == 0)
{
remaining = indices.Length;
}
Swap(random.Next(remaining--), remaining);
return indices[remaining];
}
public int Remaining() => remaining;
public int this[int i] => indices[i];
private void Swap(int i, int j)
{
var tmp = indices[i];
indices[i] = indices[j];
indices[j] = tmp;
}
}
With the IndexShuffler class, we can now make a simple wrapper class in order to actually select actual elements from some generic source IList<T>.
RandomSelector.cs
#if DEBUG
using System;
#endif
using System.Collections.Generic;
public class RandomSelector<T>
{
private IndexShuffler shuffler;
private IList<T> values;
/// <summary>
/// Create an instance with the specified list of source values.
/// </summary>
/// <param name="values">The source list of values to select from.</param>
public RandomSelector(IList<T> values)
{
#if DEBUG
if (values == null)
{
throw new ArgumentNullException("values == null");
}
#endif
shuffler = new IndexShuffler(values.Count);
this.values = values;
}
/// <summary>
/// Selects a specified number of random non-repeating values from the source list.
/// The specified count should not exceed the size of the source list.
/// Once all values have been selected, the function should no longer be called.
/// </summary>
/// <param name="count">The number of values to randomly select.</param>
/// <returns>An array containing the random selection of values.</returns>
public T[] Select(int count)
{
#if DEBUG
if (count < 0)
{
throw new ArgumentOutOfRangeException("count < 0");
}
#endif
var selected = new T[count];
shuffler.Shuffle(count);
while (count-- != 0)
{
selected[count] = values[shuffler[shuffler.Remaining() + count]];
}
return selected;
}
/// <summary>
/// Selects a specified number of random non-repeating values from the source list.
/// The specified count can exceed the size of the source list.
/// Selected values will not repeat until all values have been selected.
/// </summary>
/// <param name="count">The number of values to randomly select.</param>
/// <returns>An array containing the random selection of values.</returns>
public T[] SelectWrap(int count)
{
#if DEBUG
if (count < 0)
{
throw new ArgumentOutOfRangeException("count < 0");
}
#endif
var selected = new T[count];
for (int i = 0; i < count; ++i)
{
selected[i] = values[shuffler.ShuffleWrap()];
}
return selected;
}
/// <summary>
/// Gets the count of values in the contained source list.
/// </summary>
/// <returns>The number of values in the source list.</returns>
public int Max() => values.Count;
/// <summary>
/// Gets the count of unselected values in the contained list.
/// </summary>
/// <returns>The number of unselected values in the contained list.</returns>
public int Remaining() => shuffler.Remaining();
}
Testing/Sample usage
using System;
using System.Collections.Generic;
using System.Linq;
public static class Program
{
public static bool TrySelectMost<T>(
RandomSelector<T> selector, int count, out T[] selected)
{
if (selector.Remaining() != 0)
{
selected = selector.Select(
count < selector.Remaining() ? count : selector.Remaining());
return true;
}
selected = null;
return false;
}
public static void TestSelect()
{
var values = Enumerable.Range(1, 9).ToList();
var selector = new RandomSelector<int>(values);
int[] selected;
if (TrySelectMost(selector, 5, out selected)) // true: selects 5 of 9 values
{
Console.WriteLine("1st selection:");
Array.ForEach(selected, v => Console.Write("{0} ", v));
}
if (TrySelectMost(selector, 10, out selected)) // true: selects remaining 4
{
Console.WriteLine("\n\n2nd selection:");
Array.ForEach(selected, v => Console.Write("{0} ", v));
}
if (TrySelectMost(selector, 10, out selected)) // false: no elements remaining
{
Console.WriteLine("\n\n3rd selection:");
Array.ForEach(selected, v => Console.Write("{0} ", v));
}
}
public static void TestSelectWrap()
{
var values = Enumerable.Range(1, 9).ToList();
var selector = new RandomSelector<int>(values);
// selects 3 random sequences based on the source values; stored contiguously
// sequences begin at indices 0 * selector.Max(), 1 * selector.Max(), etc.
var selectedWrap = selector.SelectWrap(selector.Max() * 3);
Console.WriteLine("\n\nwrap selection:");
Array.ForEach(selectedWrap, v => Console.Write("{0} ", v));
}
public static void TestNoRepeat(int valueCount, int iterations)
{
var values = Enumerable.Range(1, valueCount).ToList();
var set = new HashSet<int>();
for (int i = 0; i < iterations; ++i)
{
var selector = new RandomSelector<int>(values);
for (int j = 0; j < selector.Max(); ++j)
{
var value = selector.Select(1)[0];
if (set.Contains(value))
{
throw new InvalidOperationException("repetition");
}
else
{
set.Add(value);
}
}
set.Clear();
}
Console.WriteLine("\n\nfinished no repeat test");
}
public static void Main(string[] args)
{
TestSelect();
TestSelectWrap();
TestNoRepeat(1000, 1000);
}
}
Randomisn't thread safe. If you have a static instance of it, you need to use some type of locking mechanism when accessing it. \$\endgroup\$ – Brad M Dec 4 '18 at 14:47