longsleep / as3-commons

Automatically exported from code.google.com/p/as3-commons
1 stars 1 forks source link

ArrayUtils.shuffle algorithm results in a biased shuffle #142

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago
What steps will reproduce the problem?
1. Run ArrayUtils.shuffle on an array

What is the expected output? What do you see instead?
I expect an array that is statistically as likely to contain one permutation as 
any other. What I actually get is an array that has a higher probability of 
certain permutations than others.

What version of the product are you using? On what operating system?
r1513 looks like the last updated version of ArrayUtils.as.

Please provide any additional information below.
The Fisher-Yates shuffle requires that 0 ≤ rand ≤ i. When it's actually 
implemented as 0 ≤ j < length, you get a biased result set. See 
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Implementation_errors.
 Below is the implementation I'm using, which as far as I can tell from looking 
at other implementations is correct:

for(var i:int = array.length - 1; i > 0; i--) {
    var j:int = Math.floor(Math.random() * (i + 1));
    var temp:* = array[i];
    array[i] = array[j];
    array[j] = temp;
}

Original issue reported on code.google.com by PERL.pro...@gmail.com on 13 Aug 2013 at 7:18

GoogleCodeExporter commented 9 years ago
Hey there,

thanks very much for this fix, I've made the changes and these are now 
available in the trunk of as3commons-lang.

Original comment by ihatelivelyids on 13 Aug 2013 at 8:06