HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMajor

Shuffling a deck

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
deckshufflingstackoverflow

Problem

My objective is to swap every element of a string array with a random element.

for (int i = 0; i < array.length; i++) { // scanning the deck
    int abc = rm.nextInt(77); // random object range
    String temp = array[i]; // swapping cards at random places
    array[i] = array[abc];
    array[abc] = temp;
}


I checked the code, and it seems to work. There’s no visible pattern of increase or decrease in the elements of the resulting array, and no repetition either. Am I right? Are there any problems in this code?

Solution

There is a problem with the distribution of your shuffle. Instead of choosing a random index from anywhere in the array, choose an index from zero to i (inclusive). This should prevent the same card from being shuffled twice* and ensure a more even distribution (think of it as being analagous to taking cards out of a deck at random and stacking them on a new pile. Once they're on the new pile, they don't move around anymore). This is essentially the Fisher-Yates shuffle.

Shuffling an array of strings "a", "b", and "c" using your algorithm, I got the following results from 100,000 runs:

abc: 14974
acb: 18531
bac: 18755
bca: 18225
cab: 14694
cba: 14821


Using the algorithm I just described, I got these results:

abc: 16515
acb: 16758
bac: 16523
bca: 16706
cab: 16788
cba: 16710


* By "prevent the same card from being shuffled twice" I mean that each card can only be the "initiator" of one swap; they can still be "displaced" by another card initiating a swap.

Context

StackExchange Code Review Q#52407, answer score: 35

Revisions (0)

No revisions yet.