具有“链环”的连续Shuffler

Question

作为一项学术练习，我决定实施一个持续的洗牌，就像在赌场黑板上看到的那样。它通过存储一个“链接循环”(一个带有最后一个链接到第一个元素的链接列表)和在删除一个项时在循环周围随机地走几步来操作。

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

但是，它似乎倾向于将列表末尾附近的项作为其第一项返回:使用以下测试代码

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
}

我得到一个黑桃最常见的第一张卡，偶尔一颗心，和俱乐部或钻石似乎从来没有。有没有办法消除我的算法中的偏差，而不完全取消对随机数生成器的限制，这样就会产生大量的步骤，从而减慢程序的速度？如果我取消了这个限制，我的测试用例将从亚毫秒运行时更改到大约0.15秒，但没有偏倚(我在LinqPad中作为测试床运行)。

Answer 1

不仅是你的第一次迭代就错了.

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

在每个循环上执行GetNextRandom，它返回一个不同的数字..。假设随机返回12，31，2。

循环1：

I=0，小于12。太好了，继续遍历链接列表。

循环2：

I=小于31的1。太好了，继续。

I= 2，不小于2，就在那里。

即使随机给了你12，你只移动了两次！希望，这是直觉，你将移动到下一个链接的平均次数较少。我不想用数学来证明这一点.我是这样想的，当x增加的时候，得到x上的连续数的机会就会减少。

如果我的解释没有意义的话，那就在Console.WriteLine中加入GetNextRandom吧。在生成每个值之前，您应该注意到随机调用的次数。

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

我认为使用无界随机数发生器可以掩盖问题。

你现在可能想知道，为什么我说，由于在每个循环上重新生成上界，你会移动更少的次数，但你说

但是，它似乎倾向于将列表末尾附近的项作为其第一项返回。

看看你是如何创建链接列表的..。在整个创建过程中，_current始终是第一项，因此您将以以下方式结束：

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

您还可以在_current中跳过Pop (返回_current.Next)，这意味着如果您按顺序弹出I5、I4、I3、I2、I1。所以你的偏见就在列表的开头。

Answer 2

至于眼前的问题，在将所有卡片加到一个随机位置后，改变初始开始位置应该可以消除偏见：

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

使用自定义类而不是匿名类。这更好地封装了您的代码，并且更容易解码您所做的事情。另外，如果你想测试不同的洗牌程序，你可以重复使用一个卡片类。

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