# Spherical forums

## Sphere Development => Resources => Topic started by: N E O on August 29, 2013, 06:13:47 pm

Title: [code] Simple array randomizer (aka shuffle)
Post by: N E O on August 29, 2013, 06:13:47 pm
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.

Code: (javascript) [Select]
`/** non-destructive randomizer **/function shuffle(arr) {	var r = arr.slice();	return r.sort(function(a,b){		return Math.random()-Math.random();	});}`

Code: (javascript) [Select]
`/** 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.
Title: Re: [code] Simple array randomizer (aka shuffle)
Post by: Radnen on August 29, 2013, 06:33:47 pm
Nicely done! There is shorter, :P

Code: (javascript) [Select]
`[1, 2, 3, 4, 5].sort(function() { return 0.5 - Math.random();});`

Edit:
Probably a little faster too now that I think about it.
Title: Re: [code] Simple array randomizer (aka shuffle)
Post by: Fat Cerberus on August 29, 2013, 11:50:00 pm
@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:

Code: (javascript) [Select]
`var r = arr.slice();`
Title: Re: [code] Simple array randomizer (aka shuffle)
Post by: N E O on August 30, 2013, 03:26:04 pm
@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.
Title: Re: [code] Simple array randomizer (aka shuffle)
Post by: Fat Cerberus on August 30, 2013, 09:46:53 pm
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.
Title: Re: [code] Simple array randomizer (aka shuffle)
Post by: N E O on July 03, 2014, 05:25:25 pm
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):

Code: (javascript) [Select]
`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.
Title: Re: [code] Simple array randomizer (aka shuffle)
Post by: Radnen on July 03, 2014, 07:52:27 pm
Yes, it has since been built into Link, thanks to Lord English. :)

Code: (javascript) [Select]
`var shuffled = Link([0, 1, 2, 3, 4]).shuffle();`
Title: Re: [code] Simple array randomizer (aka shuffle)
Post by: Fat Cerberus on July 04, 2014, 10:06:15 pm
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!