Array randomizer, both non-destructive (by copy) and destructive (in-place). It's quite possibly the shortest way to write a shuffle and I can't believe I didn't realize it until now.
/** non-destructive randomizer **/
function shuffle(arr) {
var r = arr.slice();
return r.sort(function(a,b){
return Math.random()-Math.random();
});
}
/** destructive randomizer **/
function shuffle(a,b){return Math.random()-Math.random();}
// ... then sort in place ...
someArray.sort(shuffle);
The two Math.random calls are really the only thing stopping it from being as fast as a normal sort function. Array.sort is inherently destructive and I wanted to operate on a copy; you can use the in-place shuffle if you don't need the copy. You can also modify the sort function to use properties of a and b like any other sort function.
Nicely done! There is shorter, :P
[1, 2, 3, 4, 5].sort(function() { return 0.5 - Math.random();});
Edit:
Probably a little faster too now that I think about it.
@NEO:
Your "non-destructive" version is still destructive. var r = arr just aliases the original array. You have to use slice to get a copy:
var r = arr.slice();
@Lord English - aaugh, really? Not a copied value? That's annoying. Code updated to use slice, thanks!
@Radnen - Yours is indeed shorter and for unweighted sorting definitely faster; mine originally started as the somewhat weighted a*Math.random()-b*Math.random(), then I decided to remove the weights because they're both still random. It made more sense my way when it was "weighted" and I'll probably edit it to restore the weights.
Yeah, an array is just an object in JS so unless you explicitly make a copy of it you're just passing a reference around.
Super bump.
How naive I was about shuffle previously! Use the Fisher-Yates (http://bost.ocks.org/mike/shuffle/) shuffle from now on (it's also faster than my original, O(n) acc. to author):
function shuffle(arr) {
var n = arr.length, t, i;
while (n) {
i = Math.random() * n-- | 0; // 0 ≤ i < n
t = arr[n];
arr[n] = arr[i];
arr[i] = t;
}
return arr;
}
Just read this post on visualizing algorithms (http://bost.ocks.org/mike/algorithms/) and it made me think of this thread, particularly the section on shuffling bias.
Yes, it has since been built into Link, thanks to Lord English. :)
var shuffled = Link([0, 1, 2, 3, 4]).shuffle();
Yeah, Fisher-Yates is the best way to shuffle. It's ridiculously simple to implement and is literally the single most efficient way to do it--and given a good RNG, all permutations are possible and equally likely to occur.
As it turns out, sort() should never be used to shuffle, since sorting algorithms are designed around the assumption that the comparison function is consistent (one that isn't, as noted in the article NEO posted, is by definition broken). Depending on the sorting algorithm used, this can even cause an infinite loop!