Fisher–Yates shuffle in C#

Question

Is this a proper C# implementation of the Fisher–Yates shuffle?

//Fisher–Yates shuffle en.wikipedia.org/wiki/Fisher–Yates_shuffle
//for i from 0 to n−2 do
//j ← random integer such that i ≤ j < n
//exchange a[i] and a[j]
int count = 52;
int[] deck = new int[count];
for (byte i = 0; i < count; i++)
    deck[i] = i;
Random rand = new Random();
// next(max) Returns a non-negative random integer that is less than the specified maximum.
for (byte i = 0; i <= count - 2; i++)
{
    int j = rand.Next(count - i);
    if (j > 0)
    {
        int curVal = deck[i];
        deck[i] = deck[i+j];
        deck[i+j] = curVal;
    }
}
//suffle the other directinon to be sure 
//for i from n−1 downto 1 do
//j ← random integer such that 0 ≤ j ≤ i
//exchange a[j] and a[i]
for (int i = count - 1; i >= 1;  i--)
{
    int j = rand.Next(i + 1);
    if (j != i)
    {
        int curVal = deck[i];
        deck[i] = deck[j];
        deck[i] = curVal;
    }
}

Answer 1

Since I'm not sure what you are asking by if you are doing it correctly I decided the quickest and easiest answer is to put your code to use. I created a method called Yates and put your code in it. I then called it 19 times in a simple for loop noted the output. (I limited my output to the first 5 numbers so it is more clear here)

35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...
35 22 23 7 25...

You'll notice it is 19 of the same thing. The problem with Random is that it isn't truly random sometimes, and you just ran across this. simple fix for me was to move the creation of the Random rand outside of the method now when I run it.

13 48 16 39 44...
20 3 10 27 18...
20 38 6 10 9...
1 28 6 33 7...
40 20 7 23 37...
31 22 0 34 18...
51 50 49 1 48...
24 1 44 37 50...
23 1 30 41 3...
41 32 45 23 11...
31 47 32 25 34...
49 8 16 33 32...
21 12 17 32 37...
8 2 40 41 49...
0 15 29 42 39...
39 0 46 20 22...
13 24 3 34 26...
9 10 43 2 39...
36 4 40 45 48...

I know it's not much to go on and I normally give much longer reviews but there isn't much code to review.

Here is the code I used to test against

void Main()
{
    for (int i = 0; i < 19; i++)
    Console.WriteLine($"    {string.Join(" ", Yates().Take(5))}...");
}
Random rand = new Random();
private int[] Yates()
{
    int count = 52;
    int[] deck = new int[count];
    for (byte i = 0; i < count; i++)
    deck[i] = i;
    for (byte i = 0; i <= count - 2; i++)
    {
        int j = rand.Next(count - i);
        if (j > 0)
        {
            int curVal = deck[i];
            deck[i] = deck[i + j];
            deck[i + j] = curVal;
        }
    }
    for (int i = count - 1; i >= 1; i--)
    {
        int j = rand.Next(i + 1);
        if (j != i)
        {
            int curVal = deck[i];
            deck[i] = deck[j];
            deck[j] = curVal;
        }
    }
    return deck;
}

EDIT

After having read everything and considered what you are trying to accomplish I believe that you are getting what are trying to accomplish. That being it looks like you are trying to shuffle a deck of 52 cards. Also with the answer you provided this gives me a little more clue as to what to try to tell you for a better review other than just spitting out the output. So here are my suggestions:

Unit Testing

All programs that are going to be used for "production" (even if production means you are playing your own game) should have some tests in place that exercise your code. Testing randomness isn't always easy but you already thought of 3 tests that you could have written outside of your win forms application.

    for (byte i = 0; i < 52; i++)
    {
        if (hsDeck.Contains(deck[i]))
            Debug.WriteLine("Houston we have a problem");
        if (deck[i] < 0)
            Debug.WriteLine("Houston we have a problem");
        if (deck[i] > 51)
            Debug.WriteLine("Houston we have a problem");
        hsDeck.Add(deck[i]);
    }

This information would have been better served in your question. But the test is simple and is simple to reproduce using MSTest, NUnit, or xUnit. The latter two being among the more popular but MSTest is built into Visual Studio. I see that you put Debug.WriteLine in your "test" so that you can watch the debug screen. Well how about instead of reading the debug screen you watch the test runner screen for a green check or red x for a pass or fail? You could even copy and paste your code but you'd run into an immediate hicup. You have testable code inside a non-testable class. Solution: extract that method into its own very small class.

public class FisherYates
{
    private static readonly Random rand = new Random();
    public static byte[] Shuffle(byte count)
    {
        //removed for brevity
        return deck;
    }
}

Now you can write your test

[TestClass]
public class FisherYatesTests
{
    [TestMethod]
    public void ShuffleWillNotPutAValueBelowZeroOrAboveCountOrReturnDuplicates()
    {
        for (int i = 0; i < 254; i++)
        {
            var shuffled = FisherYates.Shuffle(52)
            if (shuffled.Any(x=> x<0))
                Assert.Fail("Algorithm returned value below zero");
            if (shuffled.Any(x=> x>51)
                Assert.Fail("Algorithm returned value higher than largest index");
            if (shuffled.GroupBy(x => x).Any(x=> x.Count() > 1))
                Assert.Fail("Algorithm returned duplicate values");
        }

    }
}

That test runs very fast. Total time on my pc to compile and run those tests as many times I want is under 3 seconds. Understanding the green or red marks takes next to nothing to understand.

Closeness to algorithm

So you noticed already that there was a bug in your code. I noticed (after having re-read the wiki) page that you implement the algorithm AS WELL AS an alternative.

The modern version of the Fisher–Yates shuffle, designed for computer use, was introduced by Richard Durstenfeld in 1964[2] and popularized by Donald E. Knuth in The Art of Computer Programming as "Algorithm P".[3] Neither Durstenfeld nor Knuth, in the first edition of his book, acknowledged the work of Fisher and Yates; they may not have been aware of it. Subsequent editions of The Art of Computer Programming mention Fisher and Yates' contribution.[4]

The algorithm described by Durstenfeld differs from that given by Fisher and Yates in a small but significant way. Whereas a naïve computer implementation of Fisher and Yates' method would spend needless time counting the remaining numbers in step 3 above, Durstenfeld's solution is to move the "struck" numbers to the end of the list by swapping them with the last unstruck number at each iteration. This reduces the algorithm's time complexity to O(n), compared to O(n2) for the naïve implementation.[5] This change gives the following algorithm (for a zero-based array).

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

An equivalent version which shuffles the array in the opposite direction (from lowest index to highest) is: (emphasis mine)

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
    j ← random integer such that i ≤ j < n
 exchange a[i] and a[j]

So to answer your question did you implement it... Yes and No. Yes: you did it twice. No: You did it twice in the same method but the algorithm says once. Does it really matter? No. You want a random deck of cards you'll get it.

Answer 2

I agree with the comment from Sevy about you should pass the array to the method. But this happens to be how I need to use it.

The answer from Robert Snyder is correct but it contains a bug in my question

This was just setting deck[i] back to itself so it was doing nothing

int curVal = deck[i];
deck[i] = deck[j];
deck[i] = curVal;

Current code

Random rand = new Random();
public MainWindow()
{
    InitializeComponent();
    //for (byte b = 0; b < 200; b++)
    //    System.Diagnostics.Debug.WriteLine(rand.Next(52));
    byte[] deck;
    HashSet<byte> hsDeck = new HashSet<byte>();
    for (byte b = 0; b < 254; b++)
    {
        deck = Shuffle(52);
        hsDeck.Clear();
        for (byte i = 0; i < 52; i++)
        {
            if (hsDeck.Contains(deck[i]))
                Debug.WriteLine("Houston we have a problem");
            if (deck[i] < 0)
                Debug.WriteLine("Houston we have a problem");
            if (deck[i] > 51)
                Debug.WriteLine("Houston we have a problem");
            hsDeck.Add(deck[i]);
        }
        Debug.WriteLine(string.Join(", ", deck));
    }
}       
private byte[] Shuffle(byte count)
{
    byte[] deck = new byte[count];
    for (byte i = 0; i < count; i++)
        deck[i] = i;
    byte curVal;
    //Fisher–Yates shuffle en.wikipedia.org/wiki/Fisher–Yates_shuffle
    //for i from 0 to n−2 do
    //j ← random integer such that i ≤ j < n
    //exchange a[i] and a[j]
    for (byte i = 0; i <= count - 2; i++)
    {
        byte k = (byte)rand.Next(count - i); //Returns a non-negative random integer that is less than the specified maximum
        if (k > 0)
        {   // exchange the values 
            curVal      = deck[i];
            deck[i]     = deck[i + k];
            deck[i + k] = curVal;
        }
    }
    //return deck;
    //suffle the other directinon to be sure 
    //for i from n−1 downto 1 do
    //j ← random integer such that 0 ≤ j ≤ i
    //exchange a[j] and a[i]
    for (byte i = (byte)(count - 1); i >= 1;  i--)
    {
        byte k = (byte)rand.Next(i + 1);
        if (k != i)
        {   // exchangethe values 
            curVal  = deck[i];
            deck[i] = deck[k];
            deck[k] = curVal;
        }
    }
    return deck;
}