4

I saw this code in Oracle documentation.

The documentation states: "The shuffle method below,unlike most naive attempts at shuffling, it's fair (all permutations occur with equal likelihood, assuming an unbiased source of randomness)".

My question is what is the purpose of variable i minus 1 within the swap method? Is - 1 really necessary for a fair randomization?

public static void shuffle(List<?> list, Random rnd) {
    for (int i = list.size(); i > 1; i--)
        swap(list, i - 1, rnd.nextInt(i));
}

3 Answers 3

5

The indexing of the array goes from 0 to its size minus 1. Because the i starts at list.size(), which is 1 more than the index of the last element, and ends at index 2, subtracting 1 from i is required. The other option is to have

 public static void shuffle(List<?> list, Random rnd) {
    for (int i = list.size() - 1; i > 0; i--)
        swap(list, i, rnd.nextInt(i+1));
}
4
  • 2
    That should be: swap(list, i, rnd.nextInt(i + 1)); otherwise you would never swap an entry to the last element in the list, and that would mean it's not a fair shuffle function. Jan 1, 2016 at 4:06
  • @ErwinBolwidt Oh, yes, you are correct, I forgot to change that. Anyway, I edited it.
    – indjev99
    Jan 1, 2016 at 4:35
  • 1
    Note regarding Oracle's comment about "fair randomization": Notice that sometimes nothing will be swapped, because the two indexes passed to swap() will be the same. The "naive attempts" they mention don't allow those indexes to be the same, so they always swap, and don't produce fair random permutations Jan 1, 2016 at 14:39
  • @MattTimmermans Yeah, if it is without that correction (the i+1 one), no element will be at its starting position.
    – indjev99
    Jan 1, 2016 at 16:47
2

Examine the problem with a list of size 10 for example. If you remove the - 1, then the first swap() to occur will run:

swap(list, 10, rnd.nextInt(10);

As there is only 10 items in the list, and you are trying to swap item 11 (due to list indexes starting at zero), the swap will fail.

1

Yes it is necessary because the list you are running through is 0 based, but the random function you are calling is not (the ceiling you pass in indicates the number of integers you want, so if you input 10 then the range of values returned is 0 through 9).

If the list has 10 items in it, then the index range is 0 to 9, when you generate a random number, you need 10 numbers so the numbers it will return are 0 to 9.

2
  • 3
    This is not correct. rnd.nextInt(i) returns a number from 0 to i-1 Jan 1, 2016 at 4:30
  • You're right. Too much river water. I will correct that last bit Jan 1, 2016 at 4:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.