How to Test if a Deck of Cards Has Been Shuffled Enough in Java

Question

I have to test and see if this method has shuffled a deck of cards. Here if the code for the actual shuffling part.

 public void randomShuffle () {
               for (int i = 0; i < DECK_SIZE; i++) {
                   int place = (int)((Math.random()*(51-i))+i);
                   Card temp = this.cardAt(i);
                   this.cardList[i] = this.cardAt(place);
                   this.cardList[place] = temp;
           }
       }

The problem with testing whether its been shuffled is that I could only switch two cards and it would be considered shuffled. Here is what i have so far for the test of the random shuffle.

static void randomShuffleTest () {
       Deck deck1 = Deck.newDeckOf52();
       Deck deck2 = Deck.newDeckOf52();
       deck2.randomShuffle();           

       assert false == deck1.equals(deck2);
    }

So, my question is, how do I test if something has been shuffled enough?

Answer 1

You can't. It's impossible to determine if a deck is shuffled because in theory the shuffling could produce a deck that is exactly in order.

Answer 2

Exact test is not possible. Just trust your algorithm. or use Collections.shuffle()

Answer 3

You cannot do this with a single sample. But what you might be able to do is to perform an statistical analysis of a number of shuffled decks to look for signs of non-randomness.

I think you might do better asking this on math.stackexchange.com ... where the brainy guys hang out. If they can explain "the math" in simple terms (for dumb IT folks like you and me), you should be able to code the tests in Java.

---

When I say "you cannot do this" ... obviously you can test to see if the deck has not been shuffled at all, or if shuffling has corrupted the deck. But neither of these are a credible test for your criteria ... "shuffled enough".

Answer 4

First of I like this question(interesting).

• First of I would like to know what is your definition off "shuffled enough?". Can you even measure it? Do you have guidlines for this? Should for example at least five cards but in a different spot? You could easily write a test to validate that a number of cards or in a different spot, but is this enough?
• I also think Mark is right about producing a shuffled deck which mimics original deck(although I doubt the probability is very low). So testing that would be very hard or you could discard the shuffled deck if it mimics original. That way your test would suffice
• Furthermore I believe you should probably use Jigar's mention of Collections.shuffle() instead of writing something yourself?

Answer 5

One measure might be to sort the shuffled deck and check how many 'operations' it took. Obviously this measure would depend on the sort algorithm.

Alternately, you might find some statistical measure somewhere here: http://en.wikipedia.org/wiki/Randomness_tests.

Answer 6

Exactly as Mark Byers said, a shuffling algorithm may produce a deck that is exactly in order. But if it does so in every successive run, then definitely it's a bad algorithm! So a proper algorithm for shuffling should create sequences of cards such that the distribution of cards on the i-th position is uniform. Let S(i)={c(1)(i),c(2)(i),...,c(54)(i)} be the i-th sequence (the i-th outcome of your algorithm). Then c(j)(i) with respect to (i) should follow (approximately) the uniform distribution. To check if that holds, run your algorithm some thousands of times, and at each position j=1,2,...,54 count the frequency in which each different card appears. The numbers should be more or less equal. Ideally, if you run the algorithm 54000 times you should see each card at each position 1000 times. I strongly doubt whether this will be the case using Math.random(). Use java.util.Random for better results. This is how you work with Random:

final java.util.Random random = new java.util.Random(seed);

and each time you need a random double:

random.nextDouble();

The method Collections.shuffle(); does exactly that. If you need RNGs better than Java's Random implementation you should most probably proceed with your own implementation.

Answer 7

The best way I found to test this is to test 1,000 or so different times and record every time the test success. Ultimately you really want to know that the test works 98-99% of the time so as long as the result are ~99% +/- 1% you should be good and the test should always pass.

• shuffled hand should not equal original.
• length of the both should be the same.
• the sum all off the cards should be the same (or similar)

example code in swift:

func testShuffled() {
    var hand1 = [3,4,5,6,7,1,2,8,9,10,11,12,2,3,4,5,6,7,8,9,10,11,12]
    var count =  0

    for _ in 0..<1000 {
        let hand2 = hand1.shuffled()

        if (hand1 != hand2 && hand1.count == hand2.count &&
            hand1.reduce(0, combine: +) == hand2.reduce(0, combine: +)) {
            count += 1
        }
        hand1 = hand2
    }
    let result = Double(count) / 1000.00
    XCTAssertEqualWithAccuracy(result, 1, accuracy: 0.02)
}