patternjavaMajor
Shuffling a deck
Viewed 0 times
deckshufflingstackoverflow
Problem
My objective is to swap every element of a string array with a random element.
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?
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
Shuffling an array of strings "a", "b", and "c" using your algorithm, I got the following results from 100,000 runs:
Using the algorithm I just described, I got these results:
* 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.
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.