Unbiased random Array shuffle

Question

When I want to shuffle an array of numbers in an array "perm" from [1...n], I wrote in Java:

int[] perm = new int[n];
for (int i = 0; i < n; i++) {
     perm[i] = i;
}

for (int i = 0; i < n; i++) {
    int new_place = (int) (Math.random()*n); // Exchange element with any random element.
    int temp = perm[new_place];
    perm[new_place] = perm[i];
    perm[i] = temp;
}

But the book wrote the randomizing code as (only change is in the for loop):

for (int i = 0; i < n; i++) {
    int new_place = i + (int) (Math.random() * (n-i)); // Exchange element with a random element to its right.
    int temp = perm[new_place];
    perm[new_place] = perm[i];
    perm[i] = temp;
}

and they say that with the code they write, they ensure that the shuffle is random by choosing uniformly from the cards not yet chosen. (Contrast to my approach, where I choose from all the cards). (I believe it's the modified version of the Fisher-Yates algorithm what they wrote).

I just want to know is my code (the above one) also unbiased for random number generation or not? If yes, why? If not, why?

(The first 2 comments are for the question that I asked if what I am doing is correct for random number generation, but I wanted to ask if it is unbiased. But I didn't know this term then, sorry. For this current question, the 4th comment has a very good link to understand).

As long as your random number generation is generating values from 0 to n, all permutations of the final array are equally likely. Your code is correct. — NeonFire, Aug 06 '21 at 22:20
Be careful casting```Math.random()``` to an ```int``` as without the parentheses it will return 0. You can declare a Random object, ```Random rand = new Random()``` and say ```int r = rand.nextInt(n)``` — NeonFire, Aug 06 '21 at 22:26
@NeonFire Sorry, I forgot to add the that the random array should be unbiased. Do you know if I should edit this question or create a new one? Thanks. — Kushal Kumar, Aug 06 '21 at 23:17
No, your algorithm (a naive shuffle) is not unbiased. Here's a good [explanation](https://blog.codinghorror.com/the-danger-of-naivete/) why not. — RaffleBuffle, Aug 06 '21 at 23:30
NeonFIre and Gene are both incorrect, RaffleBuffle's link explains it and saka1029's answer demonstrates it in the sample output. When you exchange an element with _any_ element the elements that are "on the left" of the current element have already been swapped at least once before, leading to more combinations than the actual possible permutations, as Jeff explains in the Coding Horror blog post. — Stephen P, Aug 07 '21 at 00:07

score 0 · Answer 1 · 2021-08-07T07:19:00.680

Your code seems to have a bias in the distribution of the generated array. The results of 6000 statistics for n = 3 are as follows.

static int[] shuffle(int n) {
    int[] perm = IntStream.range(0, n).toArray();
    for (int i = 0; i < n; i++) {
        int new_place = (int) (Math.random()*n);
        int temp = perm[new_place];
        perm[new_place] = perm[i];
        perm[i] = temp;
    }
    return perm;
}

public static void main(String[] args) {
    Map<int[], Integer> counts = new TreeMap<>(Arrays::compare);
    int n = 3;
    for (int i = 0; i < 6000; ++i)
        counts.compute(shuffle(n), (k, v) -> v == null ? 1 : v + 1);
    counts.entrySet()
        .forEach(e -> System.out.println(
            Arrays.toString(e.getKey()) + "=" + e.getValue()));
}

output:

[0, 1, 2]=865
[0, 2, 1]=1113
[1, 0, 2]=1161
[1, 2, 0]=1093
[2, 0, 1]=873
[2, 1, 0]=895

[0, 1, 2] and [2, 1, 0] appear to be infrequent.

When executed with the code of the book, it becomes as follows.

static int[] shuffle(int n) {
    int[] perm = IntStream.range(0, n).toArray();
    for (int i = 0; i < n; i++) {
        int new_place = i + (int) (Math.random() * (n-i));
        int temp = perm[new_place];
        perm[new_place] = perm[i];
        perm[i] = temp;
    }
    return perm;
}

output:

[0, 1, 2]=987
[0, 2, 1]=978
[1, 0, 2]=1014
[1, 2, 0]=994
[2, 0, 1]=1041
[2, 1, 0]=986

I can't explain why it is, but you should try it.

Unbiased random Array shuffle

1 Answers1