Shuffling array in Java using Random.nextInt two times

Question

Is an array of integers correctly shuffled when using Random.nextInt two times for interchanging two values?

Example code:

    Random rand = new Random();
    for (int i = 0; i < values.length; i++) {
        nIndexOld = rand.nextInt(values.length);
        nIndexNew = rand.nextInt(values.length);

        nTempValue = values[nIndexOld];
        values[nIndexOld] = values[nIndexNew];
        values[nIndexNew] = nTempValue;
    }

http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array — Jordi Castilla, Oct 22 '15 at 12:01

score 1 · Answer 1 · edited May 23 '17 at 11:58

No, your algorithm cannot give homogeneous distribution of possible permutations. See the explanation of the similar error in the section "Implementation errors":

This can be seen from the fact that doing so yields nⁿ distinct possible sequences of swaps, whereas there are only n! possible permutations of an n-element array...

Your case is a little different, but the same logic can be applied. On each iteration step you generate two randoms (0...n-1), so there are n * n possible array changes that can be applied. You do this n times. So, the total number of paths that you can go with equal probability is (n * n)ⁿ, but there are n! possible permutations.

For example, you have three elements. On each step there are 3 * 3 = 9 ways to change your current state. Doing that three times gives 9 * 9 * 9 = 729 possible ways to change initial array. It would be perfect to have equal number of all possible permutations in that set. However, there are 3! = 6 possible different final results. The number of generated permutations 729 is not divisible by 6. So for sure some permutations have higher chance to be chosen.

For proper Java implementations of the modern version of the Fisher–Yates shuffle see for example Random shuffling of an array

score 0 · Answer 2 · answered Oct 22 '15 at 11:54

0

Better limiting nextInt to the size of the incoming array

Random rand = new Random();
for (int i = 0; i < values.length; i++) {
    nIndexOld = rand.nextInt(values.length);
    nIndexNew = rand.nextInt(values.length);

    nTempValue = values[nIndexOld];
    values[nIndexOld] = values[nIndexNew];
    values[nIndexNew] = nTempValue;
}

answered Oct 22 '15 at 11:54

Filippo Fratoni

379
2
7

Sure, you're right, I corrected it in the question. But is it correct otherwise? – squarebrackets Oct 22 '15 at 11:55
Such algorithm does not give equal probability for all permutations. Some results have higher chance to be chosen. – Orest Hera Oct 23 '15 at 18:31

score 0 · Answer 3 · answered Oct 22 '15 at 11:56

0

If in your example

values.length = 40

Then yes the array is indeed shuffled properly.

answered Oct 22 '15 at 11:56

Sjoerd

186
1
5

Shuffling array in Java using Random.nextInt two times

3 Answers3