Issue 142 in as3-commons: ArrayUtils.shuffle algorithm results in a biased shuffle

[as3-c...@googlecode.com]

Status: New
Owner: ----
Labels: Type-Defect Priority-Medium

New issue 142 by PERL.pro...@gmail.com: ArrayUtils.shuffle algorithm
results in a biased shuffle
http://code.google.com/p/as3-commons/issues/detail?id=142

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;
}

--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings

[as3-c...@googlecode.com]

Updates:
Status: Fixed

Comment #1 on issue 142 by ihatelivelyids: ArrayUtils.shuffle algorithm

results in a biased shuffle
http://code.google.com/p/as3-commons/issues/detail?id=142

Hey there,

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