ArrayUtils.shuffle algorithm results in a biased shuffle
Closed this issue · 1 comments
GoogleCodeExporter commented
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
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
- Changed state: Fixed