Beware with Array shuffle function


/ Published in: ActionScript 3
Save to your folder(s)

The function "shuffle" found here (http://snipplr.com/view/11307/as3-randomize-array/) works but one should know that it doesn't produce an even randomization. In the exemple above, the array length is 6, so each item should have a probability of 1/6 to be found at any place in the randomized result. It's not the case. I built the following test to convince myself.

What it does is run 1 million times the shuffle function and count the occurences of each item at each position (on a "1" basis : if an item as a total of 1, it means it has been counted 1Million times). So at the end the count should be close to 0.2 (1/5, since there are 5 items in my array), and 1Million is enough to observe the convergency of the stats toward the ideal probability.

Well it's not the case, here's the result :
0.1497560000001291,0.1800500000001594,0.5317489999944534,0.1001570000000795,0.038288000000017634
0.1017590000000811,0.5722769999956188,0.14140800000012074,0.11653400000009588,0.06802200000004736
0.6104649999967169,0.07093600000005028,0.1350720000001144,0.07931400000005866,0.10421300000008356
0.0787610000000581,0.10652100000008587,0.11227400000009162,0.6123389999967708,0.09010500000006945
0.05925900000003861,0.07021600000004956,0.07949700000005884,0.091656000000071,0.6993719999992735
Meaning that in first position :
0 has a probability of 0.149 to appear,
1 has a probability of 0.18 to appear,
2 has a probability of 0.53 to appear,
3 has a probability of 0.1 to appear,
...

Tryed the same test with the randomize function found here : http://snipplr.com/view/11307/as3-randomize-array/, here is the result :
0.20009000000017943,0.20004000000017938,0.19958500000017892,0.19994400000017928,0.20034100000017968
0.19989300000017923,0.2002720000001796,0.19974100000017908,0.20004100000017938,0.2000530000001794
0.20008600000017943,0.19944100000017878,0.20007700000017942,0.2002600000001796,0.20013600000017948
0.199649000000179,0.2001730000001795,0.20064600000017999,0.20010900000017945,0.19942300000017876
0.20028200000017962,0.20007400000017941,0.1999510000001793,0.19964600000017899,0.2000470000001794

This is the expected result. Conclusion : if you want an even randomization you should consider an other function than the "shuffle" one.


Copy this code and paste it in your HTML
  1. function shuffle($a:Array):Array
  2. {
  3. return $a.sort( function ($a,$b):int
  4. {
  5. var sortNum : int = Math.round(Math.random() * 2) - 1;
  6. return sortNum;
  7. });
  8. }
  9.  
  10. var count:Array = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]];
  11. var tmp:Array;
  12. for (var i=0; i<1000000; i++) {
  13. tmp = shuffle([0,1,2,3,4]);
  14. count[0][(tmp[0]) ] += 1/1000000;
  15. count[1][(tmp[1]) ] += 1/1000000;
  16. count[2][(tmp[2]) ] += 1/1000000;
  17. count[3][(tmp[3]) ] += 1/1000000;
  18. count[4][(tmp[4]) ] += 1/1000000;
  19. }
  20. for each (var posI:Array in count) {
  21. trace(posI);
  22. }

URL: http://snipplr.com/view/11307/as3-randomize-array/

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.