As an academic exercise, I decided to implement a continuous shuffler, as seen on casino blackjack tables. It operates by storing a "linked loop" (a linked list with the last element linked to the first) and walking a random number of steps around the loop when an item is removed.
public abstract class BaseShuffler<T>
{
///<summary>Returns a random int in the range [0,max)</summary>
protected abstract int GetNextRandom(int max);
private Node _current = null;
private int _count = 0;
public int Count
{
get { return _count; }
}
public void Add(T value)
{
var newNode = new Node(value);
if (_count <= 0)
{
//form the loop
_current = newNode;
_current.Next = _current;
}
else
{
//insert into loop after current node
var next = _current.Next;
_current.Next = newNode;
newNode.Next = next;
}
_count++;
}
public T Pop()
{
if (_count <= 0)
throw new InvalidOperationException("Shuffler is empty");
//walk a random number of steps round the loop
for (int i = 0; i < GetNextRandom(_count); i++)
{
_current = _current.Next;
}
//remove next node from loop
var next = _current.Next;
var nextnext = _current.Next.Next;
_current.Next = nextnext;
_count--;
if (_count <= 0)
{
//remove circular reference so we don't break refcounting for GC
_current.Next = null;
_current = null;
}
return next.Value;
}
private class Node
{
public Node Next { get; set; }
public T Value => _value;
private readonly T _value;
public Node(T value)
{
_value = value;
}
}
public bool Any()
{
return _count > 0;
}
}
public sealed class Shuffler<T> : BaseShuffler<T>
{
private Random _random;
public Shuffler()
{
_random = new Random();
}
public Shuffler(int seed)
{
_random = new Random(seed);
}
protected override int GetNextRandom(int max)
{
return _random.Next(max);
}
}
However, it appears to have a bias towards the returning an item near the end of the list as its first item: using the following test code
void Main()
{
var shuffler = new Shuffler<(Rank rank, Suit suit)>();
foreach (Suit suit in Enum.GetValues(typeof(Suit)))
foreach (Rank rank in Enum.GetValues(typeof(Rank)))
{
shuffler.Add((rank, suit));
}
while (shuffler.Any())
{
var card = shuffler.Pop();
Console.Out.WriteLine($"{card.rank} of {card.suit}");
}
}
enum Suit
{
Clubs,
Diamonds,
Hearts,
Spades
}
enum Rank
{
Two = 2,
Three,
Four,
Five,
Six,
Seven,
Eight,
Nine,
Ten,
Jack,
Queen,
King,
Ace
}
I get a Spade most commonly as the first card, occasionally a Heart, and Clubs or Diamonds seemingly never. Is there a way to remove the bias from my algorithm without entirely removing the limit on the random number generator, which could then produce a large number of steps to take, slowing the program down? If I remove the limit, my test case changes from sub-millisecond runtime to around 0.15 seconds - but without the bias (I'm running in LinqPad as a test bed).
