Javascript shuffle

Submitted by wrwrwr on Fri, 01/18/2008 - 09:47

A couple of days ago I've been asked how to permute an array in JavaScript. There are a few of solutions on the web, but none so clean as the following one ;)

It is an implementation of a modern version of the Fisher-Yates algorithm. It uses the (too weak) standard pseudo-random number generator, so the resulting permutations are not really uniformly distributed; however that shouldn't matter for all but cryptographic applications.

The script at work:

Here's the shuffle function:

/** 
 * Randomly permutes an array.
 * In-place, modern version of the Fisher-Yates algorithm.
 * The default prng is usually (way) to weak for every permutation 
 * to be a possible outcome.
 */
function shuffle(array) {
	var n = array.length, k, t;
	if (n == 0) return false;
	while (--n) {
		k = Math.floor(Math.random() * (n+1));
		t = array[n];
		array[n] = array[k];
		array[k] = t;
	}
}

And here's how it is used:

var a = new Array(10);
for (var i = 0; i < a.length; i++) 
	a[i] = i;
shuffle(a);
document.writeln('<p>' + a.join(', ') + '</p>');
 
var b = 'Work is the curse of the drinking classes.'.split(/\s+/);
shuffle(b);
document.writeln('<p>' + b.join(' ') + '</p>');

Attachment	Size
shuffle.js.txt	655 bytes

Comments

Post new comment

Latest image

Comparison of texture mapping heuristics

Latest commit

UFO:AI/trunk, rev. 39

Derived another heuristic for approximating UV texture mapping with .map mapping; this new algorithm is optimal in some (rather artificial) sense, does a lot better when exact conversion is not possible, but is also a lot slower compared to the old method. Coded a general profiling decorator that should be useful for other projects too (in its simplest one may just say @profile before a function, but it can take some arguments and even simulate count of positional arguments of the original function to work around some code that checks it). Fixed exporting attributes with double quotes and made a quick patch fixing grouped objects not appearing on exported maps.