Continuous Shuffler with "linked loop"

Question

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).

Answer 1

It's not only your first iteration that's wrong...

for (int i = 0; i < GetNextRandom(_count); i++)
{
 _current = _current.Next;
}

You're executing GetNextRandom on every loop, which returns a different number... Say that the random returns 12, 31, 2.

Loop 1:
i = 0 which is less than 12. Great, keep walking the linked list
Loop 2:
i = 1 which is less than 31. Great, keep going.
Loop 3:
i = 2 which is not less than 2. Stop there.

Even though the random gave you 12, you've only moved twice! Hopefully, it's intuitive that you're going to move to the next link fewer times on average. I don't feel up to the maths to prove this... I think of it like this, the chance of getting consecutive numbers all over x decreases as x increases.

If my explanation doesn't make sense, chuck a Console.WriteLine in GetNextRandom. You should notice a random number of calls before each value is produced.

You should be doing something like:

int max = GetNextRandom(_count);
for (int i = 0; i < max; i++)
{
 _current = _current.Next;
}

I think using an unbound random number generator just hides the problem.

---

You may be wondering now why I said you're going to move fewer times as a result of regenerating the upper bound on each loop but you said

However, it appears to have a bias towards the returning an item near the end of the list as its first item

Look at how you're creating your Linked List... _current stays as the first item throughout the creation so you end up with:

I1 -> I5 -> I4 -> I3 -> I2

You also skip _current in your Pop (you return _current.Next) which means that if you pop in order you get I5, I4, I3, I2, I1. So your bias is toward the beginning of the list.

Answer 2

As for the immediate problem, changing the initial start position, after all the cards have been added, to a random position should remove the bias:

public void SetStart()
{
 int limit = GetNextRandom(_count)
 for (int i = 0; i < limit; i++)
 {
 _current = _current.Next;
 }
}

Use custom classes rather than anonymous classes. This encapsulates your code better and it is easier to decode what you've done. Also now if you want to test different shufflers you can re-use a Card class.

public class Card
{
 public enum Suit
 {
 Clubs,
 Diamonds,
 Hearts,
 Spades
 }
 public enum Rank
 {
 Two = 2,
 Three,
 Four,
 Five,
 Six,
 Seven,
 Eight,
 Nine,
 Ten,
 Jack,
 Queen,
 King,
 Ace
 }
 public Rank rank { get; set; }
 public Suit suit { get; set; }
 public Card() { }
 public Card(Suit suit, Rank rank)
 {
 this.rank = rank;
 this.suit = suit;
 }
 public Card(int deckPosition)
 {
 rank = (Rank)((deckPosition % 13) + 2);
 suit = (Suit)(deckPosition / 13);
 }
 public override string ToString()
 {
 return $"{rank} of {suit}";
 }
}

• Jesse C. Slicer: One thought - I'd probably remove the setters and the empty constructor. A card (in terms of its rank and suit) is immutable. Then the neverending deck can be implemented as a collection of cards.
• user33306: @JesseC.Slicer - If I'm not mistaken, when you try to create a collection of objects, an empty constructor is needed to initialize the collection with the new operator`