Shuffle
Created 2009-10-02T06:58:28.441Z, last edited 2009-10-08T04:49:12.592Z
This was something that I came across last week when I was doing a Flash training module for the Wimbledon Lawn Tennis Association.
In their final training module they wanted to ask random questions from various pools of questions. I.e. section 1 would have 6 question, 2 of which should be asked, section 2 might have 4 question 3 of which should be asked etc. A simple way of doing this is to shuffle the questions in each section and then take off the first n questions. JavaScript though doesn't have a shuffle function for arrays/lists, so how do you shuffle? Here are two alternative implementations:
Array.prototype.shuffle1 = function() {
for ( var n = this.length; n > 1; ) {
var k = Math.floor(Math.random()*(n--));
var t = this[k];
this[k] = this[n];
this[n] = t;
}
return this;
}
Array.prototype.shuffle2 = function() {
for ( var n = this.length; n > 1; --n) {
var k = Math.floor(Math.random()*(n+1));
var t = this[k];
this[k] = this[n];
this[n] = t;
}
return this;
}
Obviously we want the shuffle to be equally likely to produce any of the possible permutations. That is, it should produce an unbiased sample from all of the possibilities.
- Are these implementations capable of producing any of the permutations?
- Is there any difference (significant — in terms of output or bias — or maybe just stylistic etc.) between the two implementations?
- Is there a better alternative?
- What limits are there to the length of the array/list that is to be shuffled?
© 2002-2025 Kirit & Tai Sælensminde. All forum posts are copyright their respective authors.
Licensed under a Creative Commons License. Non-commercial use is fine so long as you provide attribution.