By a strange co-incidence, this was one of the questions on this year's Google Code Jam - to write some code that would distinguish between your algorithm and an unbiased shuffling algorithm.
You've mis-implemented the Fisher-Yates algorithm in a very common way, which has a known bias - elements of the array tend to end up further down the list than they started.
Here's some code that'll test the bias. It includes a version of your algorithm that's been modified to work with arbitrary sized int arrays, and a corrected version of that algorithm (basically just a standard Fisher-Yates algorithm).
import java.util.concurrent.ThreadLocalRandom;
public class Shuffler {
public static final int TEST_ARRAY_SIZE = 1000;
public static final int ITERATION_COUNT = 1000;
// OP's algorithm, modified to use int arrays
public static void badShuffle(int[] array) {
for (int i = 0; i < array.length; i++) { // scanning the deck
int j = ThreadLocalRandom.current().nextInt(array.length); // random object range
int temp = array[i]; // swapping cards at random places
array[i] = array[j];
array[j] = temp;
}
}
// Correct Fisher-Yates shuffle
public static void goodShuffle(int[] array) {
for (int i = 0; i < array.length; i++) { // scanning the deck
int j = ThreadLocalRandom.current().nextInt(array.length - i); // random object range
int temp = array[i]; // swapping cards at random places
array[i] = array[i + j];
array[i + j] = temp;
}
}
public static int testShuffling(Algorithm algo) {
// Initialise array
int[] testArray = new int[TEST_ARRAY_SIZE];
for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
testArray[i] = i;
}
// Shuffle it
algo.shuffle(testArray);
// And test the shuffling
int accumulator = 0;
for (int i = 0; i < TEST_ARRAY_SIZE; i++) {
if (testArray[i] < i) accumulator += 1;
else if (testArray[i] >i) accumulator -= 1;
}
return accumulator;
}
public static void main(String[] args) {
int n = 0;
for (int i = 0; i < ITERATION_COUNT; i++) {
if (testShuffling(Shuffler::badShuffle) < 0) n += 1;
}
System.out.println("Bad algorithm has negative skew " + n * 100.0 / ITERATION_COUNT + "% of the time");
n = 0;
for (int i = 0; i < ITERATION_COUNT; i++) {
if (testShuffling(Shuffler::goodShuffle) < 0) n += 1;
}
System.out.println("Good algorithm has negative skew " + n * 100.0 / ITERATION_COUNT + "% of the time");
}
public interface Algorithm {
public void shuffle(int[] array);
}
}
It shuffles a list of integers, and then counts how many of the integers have moved up the list, and how many have moved down, and produces a score which is the the difference between these two.
In a fair shuffle, you'd expect this score to be around zero, so it'd be positive roughly half the time, and negative roughly half the time. However, running the test with TEST_ARRAY_SIZE = 1000
, you'll probably get something like:
Bad algorithm has negative skew 99.9% of the time
Good algorithm has negative skew 47.2% of the time
With TEST_ARRAY_SIZE = 78
(which I think is the size of deck you were using - presumably you're shuffling a tarot deck), things aren't much better:
Bad algorithm has negative skew 76.9% of the time
Good algorithm has negative skew 46.7% of the time
If you're determined to write your own code, I believe the algorithm in goodShuffle
is correct. However, as others point out, you really are better off just using Collections::shuffle
.