Reverse Fisher-Yates Shuffle in C#

Question

I'm trying to create a console program to simulate having a deck of cards, the user should be able to;

• Pick a number of cards at random
• Shuffle the deck
• Return the deck to its original state

I'm struggling to figure out a way to return the deck to its starting point

When I try to just initialize the array again using; string[] Deck = { x,x,x } it doesn't seem to like that either

Any pointers would be greatly appreciated! Code below;

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

Answer 1

Simply assigning your array to a copy of the original is probably the easiest way to handle this. Having said that, it's informative to sort it using Array.sort() and a custom comparator function because you may want to maintain state of cards in the future (see below):

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

Try it!

This should illustrate some design issues with your program you'll likely be confronting soon. The issue is that the sort needs to parse strings in order to determine the rank and suit of each card. This will be problematic for writing game logic; you'll be spending a lot of energy doing parsing instead.

To resolve this, I recommend writing a struct or class to encapsulate a card. Member properties could be Rank and Suit with corresponding getters and setters, as applicable. This refactor will pay off in spades (!) in the long run. A Deck class is also appropriate and contains a member array of Cards as well as Sort and Shuffle functions.

Also, your shuffle code seems biased; check pseudocode on Wikipedia and try re-implementing it until you can get an unbiased sort running it on large data sets. Here's a sample distribution of running the sort on a dataset a few hundred thousand times and keeping a count of where elements wind up (an unbiased sort would provide an even distribution):

111258
104215
99394
96347
95288
95949
98992
104344
111426

Answer 2

Initialize your Deck in Sort function like that:

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

}

And in your Main:

string[] Deck = new string[ 52 ];

Sort( ref Deck );

Random r1 = new Random();

.....
.....

Answer 3

Try tracking the swap positions as you shuffle, undo by iterating backwards; like this:

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

Usage:

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

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

shuffleBag.Reset();

Answer 4

If you insist on unshuffling a shuffled deck, then this is the easiest way:

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