6
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Random isn'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
  • \$\begingroup\$ As a minor semantical argument, I would rephrase your description. You are not, in fact, "selecting random elements from a list", but rather "selecting (sequential) elements of a randomly ordered list". The latter inherently implies that no repetition occurs (when there are no duplicates in the starting list). When you think about it in the second way, you (or others) are less likely to overlook the repetition that is inherent to purely random selections. \$\endgroup\$ – Flater Dec 6 '18 at 11:46
3
\$\begingroup\$

There is still something more...


Warning: working with source collection

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

Usually it's a very bad idea to work with the source collection because a lot of strange things may happen. It could be cleared from outside or reduced in size, or grow. This will lead to very weird exceptions. Unless it's intended you should create a copy of it or at least use one of the immutable collections.


Dependency incjection missing

I find it's a good design choice to separate the IndexShuffler and the RandomSelector selected. You could make this even better by creating a IIndexer interface and pass this one as a dependency to the RandomSelector. It'll be easier to test because you could use a Mock and assert that everything is called as expected.

This however would require changing the name of RandomSelector to ValueSelector because now it's no longer guarateed that it's random. It could be anything and the new IIndexer doesn't have to be random anymore. This would also make testing easier because you could create some more predictible IIndexer. And when you decide to use a new, better IndexShufler, it'd be much easer to replace it.


IEnumerable interface missing

I prefer RandomSelector<T> would implement the IEnumerable<T> interace so that I can use it more the LINQ-way and query its values with .Take(10) instead of using the Select method which by the way should also be named Take. Select is a projection extension/method so seeing it here not doing this is unexpected.


More separation

I find that SelectWrap should be an IIndexer decorator for the simple Select.

\$\endgroup\$
  • \$\begingroup\$ You're certainly right about the source collection - that's rather important. \$\endgroup\$ – Henrik Hansen Dec 6 '18 at 6:04
3
\$\begingroup\$

There is some "noise" in your code, so it's a challenge to read it.


 #if DEBUG
      if (values == null)
      {
        throw new ArgumentNullException("values == null");
      }

 #endif

Why do you only want to check the input in debug mode?


The name IndexShuffler for that class is a little misleading and so are the names for its methods Shuffle() and ShuffleWrap() in that it's not a shuffle it performs. It's more like about selecting a random index or indices, so I would call it RandomIndexer.

I like the way you secure the uniqueness until all indices have been selected, but why iterate backwards?


  indices = new int[size];
  // did not use Enumerable.Range() to avoid having a call to ToArray()
  for (int i = 0; i < size; ++i)
  {
    indices[i] = i;
  }

I don't see what you mean by "avoid having a call to ToArray()" - If you do like this:

indices = Enumerable.Range(0, size).ToArray()

it's the same thing (almost).


    selected[count] = values[shuffler[shuffler.Remaining() + count]];

A construct like this tells me, that the interface or division of work is not right between RandomSelector and IndexShuffler. When you have to call a method of shuffler (the indexer) with a method on shuffler is signals that something is wrong and you should maybe rethink the design.


I don't like that you have a class with two methods that operate on the same set of data but in two different ways: Select() and SelectWrap(), but it may be intentional?

You can restrict the use to one of the behaviors by providing a flag in the constructor to RandomSelector:

public RandomSelector(IList<T> list, bool allowWrap = false) {}

and then only have one Select(int n) method. The inner algorithm for the two behaviors are almost identical except for the stop condition.


public T[] Select(int count)
{
   ...

Instead of returning T[] you could consider returning IEnumerable<T> instead in a way like this:

public IEnumerable<T> Select(int count)
{
  if (count < 0)
  {
    throw new ArgumentOutOfRangeException("count < 0");
  }

  shuffler.Shuffle(count);

  while (count-- != 0)
  {
    yield return values[shuffler[shuffler.Remaining() + count]];
  }
}

It is more flexible this way.


public int Remaining() => remaining;

In IndexShuffler isn't it only valid for Shuffle()? As I understand it ShuffleWrap() has infinite number of remaining indices?

RandomSelector<T>.Select(int n) fails if n > remaining. Maybe I would return the remaining values or null if no remaining - a behavior like Stream.Read(). And then it could have a flag IsDone that signals if it has no more items.


I'm not sure I would separate the index selection from the main class, because it's actually the only thing that changes (the index), so doing everything in one class seems to be alright.

But if insisting on a separate indexer class I think I would implement IEnumerator<int>, so that I can call it like this:

public IEnumerable<T> Select(int count)
{
  int counter = 0;
  while (counter < count && m_indexer.MoveNext())
  {
    yield return m_list[m_indexer.Current];
    counter++;
  }
}

and the entire RandomSelector class could look something like:

  public class RandomSelector<T>
  {
    IList<T> m_list;
    RandomIndexer m_indexer;

    public RandomSelector(IList<T> list, bool allowWrap = false)
    {
      m_list = list;
      m_indexer = new RandomIndexer(list.Count, allowWrap);
    }

    public bool AllowWrap => m_indexer.AllowWrap;

    public void Reset()
    {
      m_indexer.Reset();
    }

    public IEnumerable<T> Select(int count)
    {
      int counter = 0;
      while (counter < count && m_indexer.MoveNext())
      {
        yield return m_list[m_indexer.Current];
        counter++;
      }
    }
  }

where the RandomIndexer is implemented as:

  public class RandomIndexer : IEnumerator<int>
  {
    int[] m_indices;
    int m_currentIndex = -1;
    bool m_allowWrap;
    Random m_rand = new Random();

    public RandomIndexer(int size, bool allowWrap)
    {
      m_indices = Enumerable.Range(0, size).ToArray();
      m_allowWrap = allowWrap;
    }

    public bool AllowWrap => m_allowWrap;
    public int Size => m_indices.Length;
    public int Current => m_indices[m_currentIndex];

    object IEnumerator.Current => Current;

    public void Dispose()
    {

    }

    private void Swap()
    {
      int i = m_currentIndex;
      int j = m_rand.Next(m_currentIndex, Size);

      int temp = m_indices[i];
      m_indices[i] = m_indices[j];
      m_indices[j] = temp;
    }

    public bool MoveNext()
    {
      m_currentIndex++;

      if (m_currentIndex >= Size)
      {
        Reset();
        if (!m_allowWrap)
          return false;

        m_currentIndex++;
      }

      Swap();

      return true;
    }

    public void Reset()
    {
      m_currentIndex = -1;
    }
  }
\$\endgroup\$
  • \$\begingroup\$ If multiple instances of RandomIndexer are generated within a certain timespan, they will have the same random seed. \$\endgroup\$ – Brad M Dec 4 '18 at 21:23
  • \$\begingroup\$ @BradM: Yes, I know, but one could claim, that that's in fact random behavior. \$\endgroup\$ – Henrik Hansen Dec 4 '18 at 21:27
3
\$\begingroup\$

Henrik already said much of what I wanted to say, but here's what I'd like to add:

  • It's good to see documentation! I would still add a brief description to each class though.
  • Instead of #if DEBUG directives, you could write a void ThrowIfNull method and mark it with a [Conditional("DEBUG")] attribute.
  • I would let IndexShuffler accept a Random instance via its constructor. This allows for deterministic behavior (passing a Random with a specific seed), which can be useful for testing and for specific use-cases.
  • Note that, when wrapping, it's possible to get the same item twice in a row. That may not be a problem, but it's something to be aware of.
  • Why are Remaining and Max methods instead of properties? Why isn't Max named Count?
\$\endgroup\$
  • \$\begingroup\$ Instead of defining a new method with conditional attribute, the build-in method Debug.Assert(value != null) could be used :) \$\endgroup\$ – JanDotNet Dec 6 '18 at 4:47
0
\$\begingroup\$

Code review outset

The already given answers are good, but I want to address something else. Your code, while functional and no doubt created with some forethought and expertise, is not very readable. There is a lot of number (and index) magic going on that is not easily readable.

Keep in mind that randomized behaviors are considerably harder to troubleshoot (compared to deterministic algorithms). I'm not saying they can't be tested, but it's easier for problem to only present themselves in certain cases (which are not consistently repoducible). This increases your need for readable code as you can't rely on shotgun programming for debugging.

I also think your solution is a bit overengineered. There is a lot of number magic in your solution that usually requires a developer to know the intended soltuion before they can read and understand it.

I want to rebuild the solution in a way that maximizes readability. The main components to enhance your readability here are:

  • Reframing the problem
  • LINQ
  • Yield return

I could take this further into the territory of thread-safety and the likes but your original code does not seem to focus on it (and you don't mention it) so I'm not delving into it either.

My answer isn't much shorter than yours. The core intention of my answer is to reduce the number magic and instead rely on well-established or well-named programming concepts that ensure that other developers quickly understand the code.


Reframing the problem

As a minor semantical argument, I would rephrase your description. You are not, as your title describes it, selecting random elements from a list. Since you're avoiding repetition, it would be more correct to say that you are selecting (sequential) elements of a randomly ordered list.

The latter inherently implies that no repetition occurs (assuming there are no duplicates in the starting list, which would also be the case for your original code).

When you think about it in the second way, you (or others) are less likely to overlook the repetition that is inherent to purely random selections. This mindset is also what leads to redesigning the shuffling algorithm.

The latter is often referred to as "randomized" instead of "random", specifically because "randomized" implies a random order of the elements and not a repeated random pick.


The shuffling algorithm

Using LINQ, this is actually not that hard:

Random random = new Random();

var shuffledList = originalList.OrderBy(x => random.Next());

The principle is simple: each element is given a random integer value, and then the list is ordered by this integer value. Therefore, you end up with a randomly shuffled list. If you now iterate over the list:

foreach(var element in shuffledList)
{
    Console.WriteLine(element.ToString());
}

You will see that it's impossible to repeat yourself. I also hope you agree that this is more readable.


Fetching more items than the list contains

Due to the pigeonhole principle, when you want to generate a longer list of (randomized) items than your original list, you're going to have to introduce double entries. However, as you described, you still want to ensure that everything is used once before the first duplicate enters the list.

This process could be broken down in three steps:

  1. Shuffle the original list
  2. Provide each element of this shuffled list sequentially until you've reached the end.
  3. Repeat.

However, there is a big pitfall here: if you first generate an infinite randomized list, you're going to end up with an infinite amount of shuffling, and thus you're never going to be able to get the resulting list.

This is where yield return saves the day. In short, the yield keyword will ensure that the method will halt when returning an item, and will only continue if and when the next item is retrieved.

If the caller stops iterating over the list, the method no longer continues its processing. If the caller keeps iterating over the list, then you keep supplying and reshuffling the list.
In your case, you will provide an infinitely long list (the caller will at some point stop asking for more items), but it's just as possible to make the list end by simply calling return in the method.


Combining the above

We can compose the three step process in code:

public IEnumerable<T> GetShuffledInfiniteList(IEnumerable<T> originalList)
{
    Random random = new Random();

    // 3. Repeat
    for(;;)
    {
        // 1. Shuffle the original list
        var shuffledList = originalList.OrderBy(x => random.Next());

        // 2. Provide each element of this shuffled list sequentially until you've reached the end.
        foreach(var element in shuffledList)
            yield return element;
    }
}

This satisfies your second requirement:

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.

However, it does not yet satisfy your first requirement:

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.

The missing factor is that my current example only works in scope of a single method call. To address this issue, we have to move the implementation to a class, and rely on a "stackable" retrieval method. However, the core logic can be maintained.


Implementing the first requirement

I added the full implementation below. The only addition here is that we track the current index to know where we left off. When the current index grows beyond the list size, the list is reshuffled and the index is reset to 0.

You can use GetElement to get a single item, or GetElements() in order to iterate over the collection for an indefinite amount of iterations.

public class ShuffledInfiniteList<T>
{
    private readonly IEnumerable<T> _originalList;
    private readonly Random _random;

    private IEnumerable<T> _shuffledList;
    private int _currentIndex;

    public ShuffledInfiniteList(IEnumerable<T> originalList)
    {
        _random = new Random();

        _originalList = originalList;
        ShuffleList();

    }

    private void ShuffleList()
    {
        _shuffledList = _originalList.OrderBy(x => _random.Next());
        _currentIndex = 0;
    }

    public T GetElement()
    {
        if (_currentIndex >= _originalList.Count())
            ShuffleList();

        var element = _shuffledList.ElementAt(_currentIndex);

        _currentIndex++;

        return element;
    }

    public IEnumerable<T> GetElements()
    {
        for (; ; ) yield return GetElement();
    }
}

Summary

This alternate version is considerably more readable as it avoind syntactically difficult to understand concepts (swapping elements in an array, complex index calculations, ...).

Just to be clear, the operations in your original code were understandable ("this number is decreased by 1"), but the intention of the operations was not easily understandable ("why is this number decreased by 1?").

\$\endgroup\$
  • \$\begingroup\$ mhmm... OP's solution isn't perfect but it was at least on the right track because it was separated. This is what I call a god-class and is nearly untestable :-| \$\endgroup\$ – t3chb0t Dec 6 '18 at 15:32
  • \$\begingroup\$ @t3chb0t: Injecting the Random via the constructor (and using an interface so it can be mocked) would alleviate the issue of testability. \$\endgroup\$ – Flater Dec 6 '18 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.