8
\$\begingroup\$

So, I took a stab at the ole C# Card Shuffle. I wanted to create my own genuine solution rather than copy someone else's. Any advice?

public class Program
{
    enum Suit
    {
        Hearts,
        Diamonds,
        Clubs,
        Spades
    }
    class Deck
    {
        public List<Card> Cards { get; set; }
        public Deck()
        {
            Cards = new List<Card>();
            foreach (Suit suit in Enum.GetValues(typeof(Suit)))
            {
                for (int y = 2; y < 11; y++)
                {
                    Cards.Add(new Card(suit, y.ToString()));
                }
                Cards.Add(new Card(suit, "A"));
                Cards.Add(new Card(suit, "J"));
                Cards.Add(new Card(suit, "Q"));
                Cards.Add(new Card(suit, "K"));
            }
        }
    }

    class Card
    {
        Suit suite { get; set; }
        string value { get; set; }
        public Card(Suit s, string v)
        {
            suite = s;
            value = v;
        }
    }
    static void Main(string[] args)
    {
        Deck myDeck = new Deck();

        List<Card> shuffleDeck = new List<Card>();
        Random r = new Random();
        int p = 0;
        while (myDeck.Cards.Count > 0)
        {
            p = r.Next(0, myDeck.Cards.Count);
            shuffleDeck.Add(myDeck.Cards[p]);
            myDeck.Cards.Remove(myDeck.Cards[p]);
        }
        myDeck.Cards = shuffleDeck;
    }
}
\$\endgroup\$
  • \$\begingroup\$ FTR: I'm on this kick of solving trivial problems that are typically asked in whiteboard interviews. Sucks that I have to dedicate my continuing education to perfecting skills that serve absolutely no purpose in the real world (whiteboard coding), but it is what it is. I've been asked to do this twice in past interviews, so I may as well actually commit an algorithm to memory. \$\endgroup\$ – Christine Jun 6 '16 at 23:23
  • \$\begingroup\$ You may be interested in this: bost.ocks.org/mike/algorithms/#shuffling \$\endgroup\$ – RobH Jun 7 '16 at 7:33
  • \$\begingroup\$ Well, I have a job, so... right now I don't need to get any job offers. Are you agreeing with me in that, it's pointless to do whiteboard interviews because being able to think up an algorithm on the spot is a pointless activity since there exist proven algorithms in the real world? \$\endgroup\$ – Christine Jul 30 '16 at 19:16
13
\$\begingroup\$

Performance

The shuffle implementation is very inefficient, as removing a random item from a list is inefficient. Searching for the element to remove is an \$O(n)\$ operation, and then removing it from the middle of the list is expensive, as the subsequent elements may have to be shifted (when the list is backed by an array).

A better algorithm is to iterate from the front or back of the list, and swap the current element with a random element in the rest of the list. Here's an example implementation going from the end of the list:

    for (var i = list.Count - 1; i > 0; i--)
    {
        var temp = list[i];
        var index = random.Next(0, i + 1);
        list[i] = list[index];
        list[index] = temp;
    }

Encapsulation

To preserve its integrity, a deck should not expose the list of cards. You could not pass this deck to Player classes safely, they might manipulate the content to rig the game.

It would be better to provide accessor methods to the necessary operations, for example:

  • take N cards
  • shuffle
  • reset

This also implies that the shuffling algorithm should not be just lying around in a main method. As shuffling is such a common task, it should be implemented in its own class, or as a list extension as demonstrated in the answer by @craftworkgames. The deck could call a shuffling implementation it trusts. Or alternatively, the shuffling implementation could be injected using the strategy pattern.

"trivial problems"

In a comment you called this a trivial problem, yet the algorithm has a serious performance issue. Don't underestimate problems that may seem trivial.

Complex software can be broken down to simple elements. Solving simple problems contributes to solving more complex problems easier in the future, and also useful for building good habits. Look at how musicians practice. The motions may seem trivial or dull, but actually very important. So goes the saying: "you play how you practice".

\$\endgroup\$
  • \$\begingroup\$ Could you explain why you want to start at the back of the list when you shuffle? \$\endgroup\$ – Gusdor Jun 7 '16 at 9:21
  • \$\begingroup\$ @Gusdor you could go from the start too, and use random.Next(i, list.Count). It's an old habit for me to go from the back, using a random generator that produces values between 0 and a limit, rather than an arbitrary range of indexes. I reworded my explanation to clarify this point, you can go from the front or back as you prefer. \$\endgroup\$ – janos Jun 7 '16 at 10:25
  • \$\begingroup\$ @janos great job in taking the time to explain your view on this. I would like to raise a point (and this may be out of scope for this problem). You say This also implies that the shuffling algorithm should be inside the class, not just lying around in a main method. I would say that the shuffle should be done in it's own class (shuffler class?). That way you can handle multiple decks and the possibility of a derived class from Deck while maintaining the air of mystery around the shuffle algorithm., \$\endgroup\$ – Peter4499 Jun 8 '16 at 3:08
  • \$\begingroup\$ @Peter4499 you're absolutely right, that paragraph was not the best. I rewrote it now, hope you'll like it better too \$\endgroup\$ – janos Jun 8 '16 at 5:18
  • \$\begingroup\$ This is intended to be a response to a whiteboard exam. Anything you write on a whiteboard is trivial. On top of that, a request for a shuffle algorithm doesn't necessarily mention how it would be implemented into a greater project... especially if it's written on a whiteboard. The performance part makes sense... though I think the difference is negligible. \$\endgroup\$ – Christine Jun 10 '16 at 20:55
5
\$\begingroup\$

I recently implemented a Shuffle method in a card game, most of the code turned out identical to yours. My Shuffle method turned out more like this:

public static class ListExtensions
{
    public static void Shuffle<T>(this IList<T> list, Random random)
    {
        for (var i = 0; i < list.Count; i++)
        {
            var temp = list[i];
            var index = random.Next(0, list.Count);
            list[i] = list[index];
            list[index] = temp;
        }
    }
}

Using this your Main method would become:

static void Main(string[] args)
{
    Deck myDeck = new Deck();
    Random r = new Random();

    myDeck.Cards.Shuffle(r);
}

Comparing it with yours I think there's a few distinct differences

  • There's no extra memory allocations (new List<Card>();)
  • The method works on any IList<T> (pro or con?)
  • The code is in a method rather than directly in Main
  • The API is fairly easy to use (in my opinion)

I'll let you decide what you like about it and take what you want. It might be better to make the Shuffle method part of the Deck class instead.

\$\endgroup\$
  • \$\begingroup\$ That is not a proper shuffle. Some will be favored over others. \$\endgroup\$ – paparazzo Aug 9 '17 at 0:00
  • \$\begingroup\$ @Paparazzi I guess that depends on your definition of a shuffle. If a human shuffled a deck of cards it's probably far less likely to be truly random since humans tend to clump cards together. A shuffling machine in a casino might do it differently again. Of course, there's also the option of running the Shuffle method multiple times. At the end of the day though, none of this really matters if the deck appears shuffled to the player. Btw.. I haven't seen your answer? You've trolled 3 other answers here and haven't even bothered to answer the question yourself. I'm curious what you'd do? \$\endgroup\$ – craftworkgames Aug 10 '17 at 11:53
  • \$\begingroup\$ A proper shuffle has the proper random distribution of hands. Troll? There is a correct answer that I have up voted. \$\endgroup\$ – paparazzo Aug 10 '17 at 11:57
  • \$\begingroup\$ @craftworkgames, one thing that I missed when implementing Fisher-Yates that you clearly have in your code but for a C# newbie, I missed is that extension methods need to be in their own class. \$\endgroup\$ – Daniel Jun 14 at 16:43
5
\$\begingroup\$

The Card class should have better naming. Properties should be UpperCamelCase, and constructor parameters should be descriptive:

public Card(Suit suit, string value)

You can declare the possible values outside of the loops because they are going to be the same each time:

public Deck()
{
    Cards = new List<Card>();
    List<string> values = Enumerable
        .Range(2, 9)
        .Select(x => x.ToString())
        .Concat(new[] { "A", "J", "Q", "K" })
        .ToList();
    foreach (Suit suit in Enum.GetValues(typeof(Suit)))
    {
        foreach (string value in values)
        {
            Cards.Add(new Card(suit, value));
        }
    }
}

If you want you can replace the loops using LINQ's query syntax:

public Deck()
{
    List<string> values = Enumerable
        .Range(2, 9)
        .Select(x => x.ToString())
        .Concat(new[] { "A", "J", "Q", "K" })
        .ToList();
    Cards =
        (from suit in Enum.GetValues(typeof(Suit))
         from value in values
         select new Card(suit, value)).ToList();
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Instead of from value in values you could simply do from value in "23456789JQKA", because string implements IEnumerable<char>. But then value would have to be a string instead of a char. \$\endgroup\$ – Anders Tornblad Jun 8 '16 at 11:15
2
\$\begingroup\$

Your shuffle will not be able to produce the entire range of shuffled decks possible.

A Random has an int32 seed value and will only be able to produce 232 (4,294,967,296) different decks. In reality there are 52! (80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000) different decks, slightly more than what Random can achieve.

To be able to generate all possible decks you must use a random source with log2(52!)≈226 bits of entropy. In C# you can use the RNGCryptoServiceProvider to get random bytes which you can combine to produce your random index for the shuffle.

I have previously posted my shuffle implementation using RNGCryptoServiceProvider for review: Shuffling an arbitrary list or sequence

\$\endgroup\$
  • \$\begingroup\$ Not correct. You just need to produce random the size of of the array multiple times. \$\endgroup\$ – paparazzo Aug 9 '17 at 0:01
1
\$\begingroup\$
  • Its inconsistent to have an enum for suit, but a string for card value. I would expect either enum or string for both.
  • At a glance, this for loop could look like 2 to 11, instead of the 2 to 10 which it is.

    for (int y = 2; y < 11; y++)
    for (int y = 2; y <= 10; y++)    // clearer to other progammers
    
  • You did not seed the Random number generator.

  • Deck should contain a Shuffle() method, because you will want to do this more than once.

\$\endgroup\$
1
\$\begingroup\$

Instead of your loop use this code:

var shuffled = myDeck.Cards.OrderBy(n => Guid.NewGuid());

It's elegant and easy and more securable. Cheers.

\$\endgroup\$
  • \$\begingroup\$ Also shuffle logics should contain only Deck class: Deck.Shuffle(); \$\endgroup\$ – alerya Jun 10 '16 at 17:59
  • \$\begingroup\$ It is applicable to any card set, not only the deck. You can shuffle even two cards. \$\endgroup\$ – Dmitry Nogin Jun 10 '16 at 18:14
  • \$\begingroup\$ GUID is unique not random \$\endgroup\$ – paparazzo Aug 9 '17 at 0:05
1
\$\begingroup\$

I removed my previous answer, as it could be modeled a way easier using singletons and reference equality. Demo:

    static void Main(string[] args)
    {
        Console.OutputEncoding = Encoding.UTF8;

        // 20 random cards from 2 decks
        var cards = Card.Deck.Concat(Card.Deck) 
            .Shuffle() 
            .Take(20) 
            .ToArray();

        // show repeated
        Console.WriteLine(string.Join(",", from c in cards
                                           group c by c into g
                                           where g.Count() > 1
                                           select g.Key));
    }

Where:

public sealed class Suit
{
    public static readonly Suit Clubs = new Suit('♣');
    public static readonly Suit Diamonds = new Suit('♦');
    public static readonly Suit Hearts = new Suit('♥');
    public static readonly Suit Spades = new Suit('♠');
    public static readonly IEnumerable<Suit> French = new[]
    {
        Clubs, Diamonds, Hearts, Spades
    };

    Suit(char symbol)
    {
        Symbol = symbol;
    }

    public override string ToString() => $"{Symbol}";
    public char Symbol { get; }
}

And:

public class Card 
{
    public static IEnumerable<Card> Deck =
        (from suit in Suit.French
         from symbol in "23456789JQKA"
         select new Card(suit, symbol)).ToArray();

    Card(Suit suit, char symbol)
    {
        Symbol = symbol;
        Suit = suit;
    }

    public override string ToString() => $"{Suit}{Symbol}";
    public Suit Suit { get; }
    public char Symbol { get; }
}

Now shuffle (thanks @aleria):

public static class Shuffling
{
    public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source) =>
        source.OrderBy(i => Guid.NewGuid());
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.