Shuffler with generics for C# This is something I am always asked by managers and clients : "make it random". More often than not, this isn't what they want. 

Comments like "I had the same element twice in a row !" and "I don't see lement X often enough !" are common, even if they are part of the "true random".

I came up with the following solution using generics. It's basically a Urn with a safeguard so the last item isn't picked after a refill. I'm looking for ways to improve it. Is it readable ? Is it efficient enough ?

using System;
using System.Collections;
using System.Collections.Generic;

namespace Utils
{
    /// &lt;summary&gt;
    /// Implements "iTunes shuffle" that is to say, it's a random where you can't get twice the same value unless you
    /// already got all the values.
    /// 
    /// To avoid having a chance to get twice the same value when refilling the pool, we store the last picked value in
    ///  `_last` and do not put it back when refilling the pool
    /// 
    /// author: ray.hubert@riseup.net
    /// &lt;/summary&gt;
    public class Shuffler&lt;T&gt; : IEnumerable
    {
        private readonly List&lt;T&gt; _allItems = new List&lt;T&gt;(); // All items used in the shuffler
        private readonly List&lt;T&gt; _pool = new List&lt;T&gt;(); // Remaining items for current series
        private T _last; //Last object extracted from the pool
        private Random _random = new Random();

        private int PoolCount
        {
            get { return _pool.Count; }
        }

        public Shuffler()
        {
        }

        public Shuffler(ICollection&lt;T&gt; allItems)
        {
            if (allItems.Count == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            _allItems.AddRange(allItems);
            PopulatePool();
        }


        public T GetNext()
        {
            if (IsPoolEmpty())
            {
                PopulatePool();
            }
            return PopRandomElement();
        }

        private T PopRandomElement()
        {
            if (PoolCount == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            int randomIndex = _random.Next(PoolCount);
            T item = _pool[randomIndex];
            _pool.RemoveAt(randomIndex);
            if (IsPoolEmpty()) _last = item;
            return item;
        }

        private void PopulatePool()
        {
            _pool.Clear();
            _pool.AddRange(_allItems);
            if (PoolCount &gt; 1) // If _allItems is size 1 we don't remove from the pool : it would be empty
            {
                RemoveLastFromPool();
            }
        }

        private void RemoveLastFromPool()
        {
            _pool.Remove(_last);
            _last = default(T);
        }

        public List&lt;T&gt; GetAllPossibleValues()
        {
            return new List&lt;T&gt;(_allItems);
        }

        private bool IsPoolEmpty()
        {
            return PoolCount == 0;
        }

        public IEnumerator GetEnumerator()
        {
            while (PoolCount &gt; 0)
            {
                yield return PopRandomElement();
            }
        }

        public void Add(T element)
        {
            _allItems.Add(element);
            PopulatePool();
        }
    }
}


Sample usage #1 :

// Loops on all alements and stop
Shuffler&lt;int&gt; shuffler = new Shuffler&lt;int&gt; {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
foreach (int number in shuffler)
{
    Console.Write("Random element : " + number);
}


Sample usage #2 :

// Loops on all elements for ever
Shuffler&lt;string&gt; shuffler = new Shuffler&lt;string&gt; {"Alice", "Bob", "John", "Bill", "Scrooge"};
bool gameIsPlaying = true;
while (gameIsPlaying)
{
    Console.Write("Random element : " + shuffler.GetNext());
}


Points I'm wanting to improve :


The empty constructor seems necessary for the Add() function to work properly (see usage)
Throwing an exception in two code path is suboptimal, I'd rather have a single place to throw it
Readability, "code-cleanness"
public class Shuffler&lt;T&gt; : IEnumerable



Why not IEnumerable&lt;T&gt;??!




        private readonly List&lt;T&gt; _allItems = new List&lt;T&gt;(); // All items used in the shuffler



The types in this line raise two red flags in my mind.


Code to the interface, not the implementation. The type of the field per se should be an interface: maybe IList&lt;T&gt;, maybe ICollection&lt;T&gt;, or maybe even something else.
With respect to maybe even something else: should it be ISet&lt;T&gt;? The explanation given for the use case suggests strongly that elements should not be repeated, because if they are repeated it's going to be complicated to avoid playing the same track twice in a row.





        private readonly List&lt;T&gt; _pool = new List&lt;T&gt;(); // Remaining items for current series



Again, code to the interface. Here IList&lt;T&gt; is justified because the ability to select by index is important for performance.




        private T _last; //Last object extracted from the pool



If "last" here means "most recent" then the methods further down seem buggy.




        private int PoolCount
        {
            get { return _pool.Count; }
        }



Are you deliberately avoiding the arrow syntax?

        private int PoolCount =&gt; _pool.Count;


is going to become increasingly common.




        public Shuffler(ICollection&lt;T&gt; allItems)
        {
            if (allItems.Count == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            _allItems.AddRange(allItems);
            PopulatePool();
        }



I concur with VisualMelon's observations on this constructor: there's no reason to prohibit empty inputs, there's no need to populate the pool yet, and there's no reason to require ICollection&lt;T&gt; rather than IEnumerable&lt;T&gt;.




        public T GetNext()
        {
            if (IsPoolEmpty())
            {
                PopulatePool();
            }
            return PopRandomElement();
        }



vs


        public IEnumerator GetEnumerator()
        {
            while (PoolCount &gt; 0)
            {
                yield return PopRandomElement();
            }
        }



Firstly, I find this API very confusing. It would make more sense to me if both methods ran forever, repopulating the pool if it runs dry.

Secondly, IsPoolEmpty() vs PoolCount &gt; 0 is inconsistent. IMO factoring out IsPoolEmpty() is overengineering: I would inline it.




        private T PopRandomElement()
        {
            if (PoolCount == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            int randomIndex = _random.Next(PoolCount);
            T item = _pool[randomIndex];
            _pool.RemoveAt(randomIndex);
            if (IsPoolEmpty()) _last = item;
            return item;
        }



You asked


  Is it efficient enough ?


Enough depends on your requirements, but the answer to the question "Is it as efficient as it could be?" is "No". _pool.RemoveAt has to shuffle along every later element in the list. In the worst case the random number generator will return a long string of 0. The standard solution is a swap.

        private T PopRandomElement()
        {
            System.Diagnostics.Debug.Assert(PoolCount &gt; 0);
            int randomIndex = _random.Next(PoolCount);
            _last = _pool[randomIndex];
            _pool[randomIndex] = _pool[PoolCount - 1];
            _pool.RemoveAt(PoolCount - 1);
            return _last;
        }


This now takes constant time rather than linear time in the size of the pool.




        private void PopulatePool()
        {
            _pool.Clear();
            _pool.AddRange(_allItems);
            if (PoolCount &gt; 1) // If _allItems is size 1 we don't remove from the pool : it would be empty
            {
                RemoveLastFromPool();
            }
        }

        private void RemoveLastFromPool()
        {
            _pool.Remove(_last);
            _last = default(T);
        }



Again, a linear removal could be replaced by a swap and a constant time removal.

But I wonder whether this actually meets the spec. Rather than removing _last from the pool entirely, didn't you just want to guarantee that it won't be the first element picked after repopulating the pool?

In fact, I'd be inclined to take this further. Suppose we refactor so that PoolCount is backed by its own field rather than _pool.Count, and that we have an additional field (or field-backed property) DelayCount.

If we replace _pool.RemoveAt(PoolCount - 1); with PoolCount--; then when PoolCount gets to 0, the pool contains the entire play list in reverse order of when they were last played. Now

PoolCount = _pool.Count;
DelayCount = N;
for (int i = 0; i &lt; DelayCount; i++)
{
    var tmp = _pool[i];
    _pool[i] = _pool[PoolCount - DelayCount + i];
    _pool[PoolCount - DelayCount + i] = tmp;
}


swaps the first N elements up to the end. Adjust the PopRandomElement method a bit more:

        private T PopRandomElement()
        {
            System.Diagnostics.Debug.Assert(PoolCount &gt; 0);
            System.Diagnostics.Debug.Assert(PoolCount &gt; DelayCount);

            int randomIndex = _random.Next(PoolCount - DelayCount);
            var tmp = _pool[randomIndex];
            _pool[randomIndex] = _pool[PoolCount - 1];
            _pool[PoolCount - 1] = tmp;

            PoolCount--;
            if (DelayCount &gt; 0) DelayCount--;

            return tmp;
        }


The effect is to guarantee that no track will repeat within N of the previous time it occurred. You can then make N settable with a public property or derive it from _pool.Count according to some hard-coded policy (e.g. a fixed percentage).




        public List&lt;T&gt; GetAllPossibleValues()
        {
            return new List&lt;T&gt;(_allItems);
        }



Why List&lt;T&gt;? In fact, is this method even useful?




        public void Add(T element)
        {
            _allItems.Add(element);
            PopulatePool();
        }



I don't see why it's desirable to populate the pool here. In addition to VisualMelon's observations, by populating the pool before reaching the end you lose the guarantee not to play the same track twice.