How to check if the crossbar of maps in Java is enough

Question

I need to check and see if this method is confused with a deck of cards. Here, if the code for the actual shuffle.

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 verifying that it has been shuffled is that I can only switch two cards, and this will be considered shuffled. Here is what I have so far tested by random shuffling.

 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 verify that something has been shuffled?

Answer 1

You cannot do this with a single sample. But what you could do is do a statistical analysis of several shuffled decks to look for signs of randomness.

I think you could better ask about it at math.stackexchange.com ... where courageous guys hang out. If they can explain the “math” in simple terms (for dumb IT professionals like you and me), you should be able to code tests in Java.

---

When I say “you can't do this” ... obviously, you can check to see if the deck is damaged at all, or if the shuffle ruins the deck. But none of them is a reliable criterion for your criteria ... "confused."

Answer 2

You can not. It is impossible to determine if the deck is confused, because theoretically shuffling can create a deck that is exactly in order.

Answer 3

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

Answer 4

One measure might be sorting the shuffled deck and checking how many “operations” have been completed. Obviously, this measure will depend on the sorting algorithm.

Alternatively, you can find some kind of statistical measure somewhere here: http://en.wikipedia.org/wiki/Randomness_tests .

Answer 5

Just like Mark Byers said, a shuffle algorithm can create a deck that is exactly fine. But if this happens in each subsequent run, then, of course, this is a bad algorithm! Therefore, the correct shuffling algorithm should create a sequence of cards, so that the distribution of cards at the i-th place is even. Let S(i)={c(1)(i),c(2)(i),...,c(54)(i)} be the ith sequence (the ith result of your algorithm). Then c (j) (i) with respect to (i) should follow a (approximately) uniform distribution. To check if this is done, run your algorithm several thousand times, and at each position j = 1,2, ..., 54 count the frequency of occurrence of each other card. Numbers should be more or less equal. Ideally, if you run the algorithm 54000 times, you should see each card in each position 1000 times. I strongly doubt whether this will be the case using Math.random() . Use java.util.Random for best results. Here's how you work with Random:

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

and every time you need a random double:

 random.nextDouble(); 

Method Collections.shuffle(); does just that. If you need RNG better than the Java Random implementation, chances are you will continue your own implementation.

Answer 6

At first I like this question (interesting).

• First, I would like to know what is your definition of “confused enough?”. Can you measure it? Do you have guidelines for this? Should, for example, at least five cards, but elsewhere? You could easily write a test to verify that several cards are in another place, but is that enough?
• I also think Mark is right about creating a shuffled deck that mimics the original deck (although I doubt the likelihood is very low). Thus, testing would be very difficult or you could refuse a shuffled deck if it imitates the original. Thus, your test will be sufficient.
• Also, I believe that you should probably use Jigar's mention of Collections.shuffle() instead of writing something yourself?

Answer 7

The best way I've found to test this is to check 1000 or so different times and record each time it succeeds. Ultimately, you really want to know that the test runs for 98-99% of the time, while the result is ~ 99% +/- 1%. You must be good and the test must always pass.

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

swift code example:

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