Skip to main content ↑ ↓
Topic: [code] Simple array randomizer (aka shuffle) (Read 63985 times) previous topic - next topic
0 Members and 1 Guest are viewing this topic.

[code] Simple array randomizer (aka shuffle)

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.

Re: [code] Simple array randomizer (aka shuffle)

Reply #1 –
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.
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

Re: [code] Simple array randomizer (aka shuffle)

Reply #2 –
@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();

Re: [code] Simple array randomizer (aka shuffle)

Reply #3 –
@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.

Re: [code] Simple array randomizer (aka shuffle)

Reply #4 –
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.

Re: [code] Simple array randomizer (aka shuffle)

Reply #5 –
Super bump.

How naive I was about shuffle previously! Use the Fisher-Yates 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 and it made me think of this thread, particularly the section on shuffling bias.

Re: [code] Simple array randomizer (aka shuffle)

Reply #6 –
Yes, it has since been built into Link, thanks to Lord English. :)

Code: (javascript) [Select]

var shuffled = Link([0, 1, 2, 3, 4]).shuffle();
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here
 

Re: [code] Simple array randomizer (aka shuffle)

Reply #7 –
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!