C#中的反转Fisher-Yates洗牌算法

Question

我正在尝试创建一个控制台程序来模拟一副牌，用户应该能够：

• 随机选择一定数量的牌
• 洗牌
• 将牌堆还原为最初状态

我正在努力想出一种方法来将牌堆返回到初始状态。

当我尝试使用 string[] Deck = { x,x,x } 再次初始化数组时，它似乎也不喜欢这样做。

如果您有任何指导意见，将不胜感激！下面是代码；

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CardArranger
{  
    class Program
    {

        static void Main(string[] args)
        {

            string[] Deck =
            {
                "D1", "D2", "D3", "D4", "D5", "D6", "D7", "D8", "D9", "D10", "DJ", "DQ", "DK",
                "H1", "H2", "H3", "H4", "H5", "H6", "H7", "H8", "H9", "H10", "HJ", "HQ", "HK",
                "C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8", "C9", "C10", "CJ", "CQ", "CK",
                "S1", "S2", "S3", "S4", "S5", "S6", "S7", "S8", "S9", "S10", "SJ", "SQ", "SK",
            };

            Random r1 = new Random();       

            while (true)
            {
                //display number of random cards
                Console.WriteLine("write shuffle to shuffle or 'sort' to organise the deck again");
                string Uinput = Console.ReadLine();

                bool isCount = int.TryParse(Uinput, out int noCards);

                if (isCount)
                {
                    for (int i = 0; i < noCards; i++)
                    {
                        Console.WriteLine(Deck[r1.Next(0, 52)]);
                    }
                }
                else
                {
                    if (Uinput.Equals("shuffle"))
                    {
                        Shuffle(ref Deck, r1);
                        Console.WriteLine("Shuffled Deck");
                        for (int i = 0; i < Deck.Length; i++)
                        {
                            Console.WriteLine(Deck[i] + " , ");                        
                        }
                        Console.WriteLine();
                        Console.WriteLine("---");
                    }
                    else if (Uinput.Equals("sort"))
                    {
                        //Implement your sort method here
                        Console.WriteLine("Sorted Deck");
                        for (int i = 0; i < Deck.Length; i++)
                        {
                            Console.WriteLine(Deck[i] + " , ");
                        }
                        Console.WriteLine();
                        Console.WriteLine("---");
                    }
                    else
                    {                    
                        Console.WriteLine("Unrecognised Command");
                    }

                }
                Console.WriteLine("Press Any Key to Repeat");
                Console.ReadKey();
            }

        }

        //Fisher-Yates Shuffle
        static void Shuffle(ref string[] OriginalArray, Random Rnd)
        {            
            for (int i = 0; i < OriginalArray.Length; i++)
            {
                string tmp = OriginalArray[i];
                int r = Rnd.Next(0, OriginalArray.Length);
                OriginalArray[i] = OriginalArray[r];
                OriginalArray[r] = tmp;
            }
        }



        static void Sort(ref string[] ShuffledArray)
        {
           // sort the deck back in order
        }
    }
}

- Mivox

---

为何不保留一个只读的原始牌组，再使用第二个牌组进行操作。复制原始牌组，您就可以重新开始了。 - Aldert

如果你真的想要排序，把它放在一个列表中并在列表上调用sort函数。 - Aldert

除了我下面的回答，这也可以使用一个“可逆”的随机数生成器来完成，参见这里：https://dev59.com/kYDba4cB1Zd3GeqPG6Qj#52656584。 - Kittoes0124

Answer 1

将数组分配给原始副本可能是处理这个问题最简单的方法。话虽如此，使用 Array.sort() 和自定义比较函数对其进行排序是具有信息性的，因为您以后可能想要维护卡片的状态（请参见下文）：

static void Sort(ref string[] ShuffledArray)
{
    Array.Sort(ShuffledArray, CardComparator);
}

public static int CardComparator(string a, string b)
{
    Dictionary<string, int> rank = new Dictionary<string, int>()
    {
        {"A", 0}, {"1", 1}, {"2", 2}, {"3", 3}, {"4", 4}, 
        {"5", 5}, {"6", 6}, {"7", 7}, {"8", 8}, {"9", 9}, 
        {"10", 10}, {"J", 11}, {"Q", 12}, {"K", 13}, 
    };
    int cmp = "HCS".IndexOf(a[0]) - "HCS".IndexOf(b[0]);

    if (cmp == 0) 
    {
        return rank[a.Substring(1)] - rank[b.Substring(1)];
    }

    return cmp;
}

试一下！

这应该说明你的程序将很快面临的一些设计问题。问题在于排序需要解析字符串以确定每张牌的等级和花色。这将对编写游戏逻辑造成问题；你将花费大量精力进行解析。

为了解决这个问题，我建议编写一个结构体或类来封装一张牌。成员属性可以是Rank和Suit，并相应地提供getter和setter。这种重构将在长期内产生巨大的回报。一个Deck类也是合适的，其中包含一个Card数组成员以及Sort和Shuffle函数。

此外，您的洗牌代码似乎存在偏差；请查看Wikipedia上的伪代码，并尝试重新实现它，直到您能够在大型数据集上运行无偏排序。以下是在数据集上运行数十万次排序并计算元素结果位置的示例分布（无偏排序将提供均匀分布）：

111258
104215
99394
96347
95288
95949
98992
104344
111426

- ggorlen

Answer 2

在Sort函数中初始化你的Deck，像这样：

static void Sort( ref string[] ShuffledArray ) {
    // sort the deck back in order
    string[] Deck =
    {
        "D1", "D2", "D3", "D4", "D5", "D6", "D7", "D8", "D9", "D10", "DJ", "DQ", "DK",
        "H1", "H2", "H3", "H4", "H5", "H6", "H7", "H8", "H9", "H10", "HJ", "HQ", "HK",
        "C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8", "C9", "C10", "CJ", "CQ", "CK",
        "S1", "S2", "S3", "S4", "S5", "S6", "S7", "S8", "S9", "S10", "SJ", "SQ", "SK",
    };


    ShuffledArray = (string[])Deck.Clone();

}

在你的Main中：

string[] Deck = new string[ 52 ];

Sort( ref Deck );

Random r1 = new Random();

.....
.....

- γηράσκω δ' αεί πολλά διδασκόμε

Answer 3

尝试在洗牌时跟踪交换位置，通过向后迭代来撤消操作，就像这样：

public sealed class ShuffleBag<T> : IEnumerable<T>, IEnumerator<T>
{
    private readonly Random m_randomNumberGenerator;
    private readonly int[] m_swaps;
    private readonly T[] m_values;

    private int m_currentIndex;
    private T m_currentValue;

    object IEnumerator.Current => Current;
    public T Current => m_currentValue;

    public ShuffleBag(Random randomNumberGenerator, T[] values) {
        if (randomNumberGenerator == null) {
            throw new ArgumentNullException(message: "random number generator cannot be null", paramName: nameof(randomNumberGenerator));
        }

        if (values == null) {
            throw new ArgumentNullException(message: "array of values cannot be null", paramName: nameof(values));
        }

        m_currentIndex = 0;
        m_currentValue = default(T);
        m_randomNumberGenerator = randomNumberGenerator;
        m_swaps = new int[values.Length];
        m_values = values;
    }

    public void Dispose() { }
    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }
    public IEnumerator<T> GetEnumerator() {
        while (MoveNext()) {
            yield return Current;
        }
    }
    public bool MoveNext() {
        if (m_currentIndex < m_values.Length) {
            var randomIndex = m_randomNumberGenerator.Next(m_currentIndex, m_values.Length);

            m_currentValue = m_values[randomIndex];
            m_swaps[m_currentIndex] = randomIndex;
            m_values[randomIndex] = m_values[m_currentIndex];
            m_values[m_currentIndex] = m_currentValue;

            m_currentIndex++;

            return true;
        }
        else {
            return false;
        }
    }
    public void Reset(bool unshuffle) {
        if (unshuffle) {
            var count = m_values.Length;

            while (0 < count--) {
                var tempValue = m_values[m_swaps[count]];

                m_values[m_swaps[count]] = m_values[count];
                m_values[count] = tempValue;
            }
        }
        else {
            var count = m_swaps.Length;

            while (0 < count--) {
                m_swaps[count] = 0;
            }
        }

        m_currentIndex = 0;
        m_currentValue = default(T);
    }
    public void Reset() {
        Reset(unshuffle: true);
    }
}

使用方法：

var shuffleBag = new ShuffleBag<string>(new Random(42), new[] { "a", "b", "c", "d", "e" });

foreach (var item in shuffleBag) {
    Console.WriteLine(item);
}

shuffleBag.Reset();

- Kittoes0124

Answer 4

如果您坚持要对已经洗牌的牌组进行还原，那么这是最简单的方法：

string[] deck =
{
    "D1", "D2", "D3", "D4", "D5", "D6", "D7", "D8", "D9", "D10", "DJ", "DQ", "DK",
    "H1", "H2", "H3", "H4", "H5", "H6", "H7", "H8", "H9", "H10", "HJ", "HQ", "HK",
    "C1", "C2", "C3", "C4", "C5", "C6", "C7", "C8", "C9", "C10", "CJ", "CQ", "CK",
    "S1", "S2", "S3", "S4", "S5", "S6", "S7", "S8", "S9", "S10", "SJ", "SQ", "SK",
};

var r = new Random();

string[] shuffled = deck.OrderBy(x => r.Next()).ToArray();

string[] unshuffled = shuffled.OrderBy(x => Array.IndexOf(deck, x)).ToArray();

- Enigmativity