11
\$\begingroup\$

The code below takes a specified number of card decks, and shuffles them according to the Fisher-Yates method. Does this implementation have any bias?

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

namespace randomShuffle
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> deck = Cards.startDeck(1);
        }
    }

    class Cards
    {
        public static List<int> startDeck(int numDecks)
        {
            List<int> initial = new List<int>();
            List<int> shuffled = new List<int>();

            //set up list of all cards in order
            while (numDecks > 0)
            {
                for (int i = 2; i <= 14; i++) //2-ace(14)
                {
                    for (int j = 0; j < 4; j++)  //each card in deck 4 times
                    {
                        initial.Add(i);
                    }
                }

                numDecks--;
            }

            //Fisher-Yates method to shuffle
            Random r = new Random(DateTime.Now.Millisecond);
            int count = initial.Count;
            for (int i = 0; i < count; i++) //go through entire unshuffled deck
            {
                //get random number from 0 to new range of unshuffled deck
                int randomDraw = r.Next(0, initial.Count);

                //take whatever is drawn and insert at beginning of shuffled list
                shuffled.Insert(0, initial[randomDraw]);

                //replace the card drawn with the end card
                initial[randomDraw] = initial.Last();

                //remove the end card from initia deck
                initial.RemoveAt(initial.Count - 1);
            }

            return shuffled;
        }
    }
}
\$\endgroup\$

3 Answers 3

7
\$\begingroup\$

Comments:

about all of your comments add close to no value to your code.

//get random number from 0 to new range of unshuffled deck
int randomDraw = r.Next(0, initial.Count);

Your comment just writes out, what your code does in the next line. This is unneccesary noise and you should not do it. The probably only acceptable comment is this one:

for (int i = 2; i <= 14; i++) //2-ace(14)

This exactly explains why you start on 2 and end with 14, the rest can be removed.

But as @Marc-Andre pointed out correctly, this comment also becomes pure noise, as soon as you extract these magic numbers to named constants:

const int LOWEST_CARD = 2;
const int HIGHEST_CARD = 14;
for (int i = LOWEST_CARD; i <= HIGHEST_CARD; i++)

Extracting methods:

Why not extract your whole shuffle algorithm to a method? This makes the code in your startDeck less cluttered. Example:

public static List<int> startDeck(int numDecks)
{
    List<int> initial = new List<int>();

    prepareDeck();

    return shuffled(initial);
}

You now exactly know, what your startDeck does.

Naming:

Your class Cards. this is definitely not nice, but that name is not OK. What does your class do? Name it after that. Try to keep your classes in SRP, they only should do one thing and nothing more.

Deck might have been better depending on what it does apart from what you posted.
Alternatively use Shuffler, Helper or similar.

Algorithm:

The english wikipedia article on the Fischer-Yates algorithm gives pretty nice pseudocode and tells us, that the algorithm is an in-place algorithm.
This means you will not need a second list to put your shuffled cards in.

//To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
      j ← random integer with 0 ≤ j ≤ i
      exchange a[j] and a[i]

this means, if you were strictly following the algorithm your code should look (something) like this:

int temp, randomNumber;
int count = initial.Count;
for (int index = count -1; index > 0; index--){
   randomNumber = r.Next(0, index+1);
   temp = initial [index];
   initial[index] = initial[randomNumber];
   initial[randomNumber] = temp;
}
return initial;
\$\endgroup\$
4
  • \$\begingroup\$ Thanks @Vogel612. My code comments are really just to help me with detailing each step of the fisher-yates method. My real concern with the above code is whether it's actually producing a acceptable randomly shuffled deck? \$\endgroup\$
    – suhMAN
    Mar 21, 2014 at 16:38
  • 1
    \$\begingroup\$ The acceptable comments to me looks like those "magic numbers" need to be extracted as variable with a proper name. This leave the comment obsolete. \$\endgroup\$
    – Marc-Andre
    Mar 21, 2014 at 17:45
  • \$\begingroup\$ But as @Malachi pointed out correctly did you mean me ? \$\endgroup\$
    – Marc-Andre
    Mar 25, 2014 at 1:42
  • \$\begingroup\$ @Marc-Andre that reminds me of the C# question, where I wrote: "there is var in c#, but unfortunately not in java"... It's definitely getting worse. fixed it now. \$\endgroup\$
    – Vogel612
    Mar 25, 2014 at 7:31
5
\$\begingroup\$

As for the random bias of the results.... your code appears to be unbiased.

The Fisher-Yates (variant) looks correctly implemented....

I would prefer if you organized the code to be more representative of the algorithm (the modern algorithm). If you need to shuffle the data in a separate list, then load all the data in to that list, and shuffle it in-place.

If you don't need the second list, then just shuffle it in-place regardless....

Shuffling in place is quite easy (assuming the data is all in data )... :

        //Fisher-Yates method to shuffle
        Random r = new Random(DateTime.Now.Millisecond);
        int count = data.Length;
        while (count > 1) //go through entire unshuffled deck
        {
            //get random number from 0 to new range of unshuffled deck
            int randomDraw = r.Next(0, count);

            //take whatever is drawn and swap it with the end of the list
            int tmp = data[randomDraw];
            data[randomDraw] = data[count-1];
            data[count-1] = tmp;

            count--;

        }
\$\endgroup\$
0
\$\begingroup\$

i repeated 4 times is not a valid deck
You have no way to know which suit it represents

shuffled.Insert(0, initial[randomDraw]);

Is O(N). Just insert and let it go in the end

shuffled.Insert(initial[randomDraw]);

You don't need to move it and then remove the last position
Just remove the position
This is a List
That method is used for an array and you don't remove
You just move just copy the card and track range down one

//replace the card drawn with the end card
initial[randomDraw] = initial.Last();

//remove the end card from initia deck
initial.RemoveAt(initial.Count - 1);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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