mercredi 15 avril 2020

How does this shuffling with Math rand work?

I saw this code to shuffle a list:

public static void shuffle(List<Integer> numbers) {
        if(numbers == null || numbers.isEmpty()) return;
        for(int i = 0; i < numbers.size(); ++i) {
            int index = (int) (i + Math.random()*(numbers.size() - i));
            swap(numbers, i, index);
        }
    }

The code seem to work but I don't understand this snippet:

            int index = (int) (i + Math.random()*(numbers.size() - i));

Basically it is i + R*(n-i) but how does this ensure that: i) we won't get an out of bounds index or ii) I won't be changing the same element's i.e. index == i and the shuffle would not be that random?




Aucun commentaire:

Enregistrer un commentaire