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

Javascript shuffle

Comments

Post new comment

Latest image

Latest commit