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, Aug 17 '16 at 07: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, Aug 17 '16 at 07: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, Aug 17 '16 at 07:22
Possible duplicate of [How to randomize (shuffle) a JavaScript array?](http://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array) — trincot, Aug 17 '16 at 08:53

Paul Hankin · Answer 1 · 2016-08-17T23:09:28.743

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.

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. — Robin Andrews, Aug 17 '16 at 14:51

Shuffling Algorithm Fair? (Javascript)

1 Answers1