Shuffling Algorithm Fair? (Javascript)

Question

I came across the algorithm below for shuffling an array in Javascript. It seems to differ from the Fisher–Yates shuffle in that the range of available "swaps" increases with the for-loop counter. This appears to be the opposite of how the Fisher-Yates version behaves. I'm curious as to whether this is a valid algorithm. Is it the Fisher-Yates in disguise? Is it biased?

If anyone could provide some code to test the frequency of the permutations it generates that would be a bonus.

<script>
var shuffle = function (myArray) {
    var random = 0;
    var temp = 0;
    console.log(myArray);
    for (i = 1; i < myArray.length; i++) {
        random = Math.round(Math.random() * i);
        console.log(random + '\n');
        temp = myArray[i];
        myArray[i] = myArray[random];
        myArray[random] = temp;
        console.log(myArray);
    }
    return myArray;
}

var arr = [1, 2, 3, 4];

shuffle(arr);

</script>

is this a valid algorithm - Yes, it does not throw any errors. — Justinas
– Justinas, Commented Aug 17, 2016 at 7:18
Not sure how to write a program to test all the permutation for a large number of trials. The results "look" fair at first glance, but I want more evidence - having read about the gross bias of the common naive solution to shuffling. — Robin Andrews
– Robin Andrews, Commented Aug 17, 2016 at 7:21
use Math.floor() instead of Math.round(), besides of that is the algorithm good and pretty common. edit: the implementations I know always iterate backwards; can't tell wether this has a significant difference. — Thomas
– Thomas, Commented Aug 17, 2016 at 7:22

Paul Hankin · Accepted Answer · 2016-08-17 23:09:28Z

3

No, it's not a fair shuffle.

Math.random() * i is a uniform random floating point value between 0 and i, but Math.round(Math.random() * i) does not pick integers between 0 and i equally. For example, when i is 2, the values in the range [0, 0.5) round to 0, values in the range [0.5, 1.5) round to 1, and values in the range (1.5, 2) round to 2. That means instead of picking 0, 1 and 2 equally often, 1 is picked with probability 0.5, and 0 and 2 are picked with probability 0.25 each.

Math.floor(Math.random * (i + 1)) would be correct.

You can verify this statistically: shuffle the array [0, 1, 2] 10000 times and see how often 2 remains at the end of the array. It should be around 3333, but because of the bias it'll be more like 2500.

Other than that, the algorithm is correct and could be described as a Fisher-Yates in reverse. You can prove it correct by induction. The base case of n=1 is trivial. The induction step is also relatively easy: if you've got a uniformly random permutation of n items, and then insert the n+1'th item at a uniformly random index from 0 to n+1, then you've got a random permutation of n+1 items.

edited Aug 17, 2016 at 23:09

answered Aug 17, 2016 at 8:49

Paul Hankin

58.8k11 gold badges99 silver badges125 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Robin Andrews Over a year ago

OK I accept the floor vs round part. However if it were to use floor, would it then be fair? It's the fact that the range of swapping positions starts small and then grows which seems radically different from the Fisher-Yates.

Paul Hankin Over a year ago

@Robin yes, I expanded my answer.

Collectives™ on Stack Overflow

Shuffling Algorithm Fair? (Javascript)

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related