An Array of Random Thoughts

Today, I was asked to supply a way (in Javascript) to create an array of all integers 0-9, but randomised, with no duplicates. Immediately, I gave this solution:

var arr = [0,1,2,3,4,5,6,7,8,9].sort(function(){
  return 0.5 - Math.random();
});

That should do it, right? Well, one of the tests that was run on the resulting “random” array was to see whether or not the first five members were consistently even or odd:

var generateRands = function(){
  return [0,1,2,3,4,5,6,7,8,9].sort(function(){
    return 0.5 - Math.random();
  });
};
var isMoreEven = function(arr){
  var i, even = 0, odd = 0;
  for (i=0; i<5; i++) {
    if (arr[i] % 2) {
      odd++;
    } else {
      even++;
    }
  }
  return even > odd;
};
var runTests = function(iterations){
  var i, even = 0, odd = 0, arr;
  for (i=0; i<iterations; i++) {
    arr = generateRands();
    if (isMoreEven(arr)) {
      even++;
    } else {
      odd++;
    }
  }
  console.log('even won', even, 'or', (even/iterations * 100) + '%',
    '; odd won', odd, 'or', (odd/iterations * 100) + '%');
};
runTests(10000);

The expected result would be that even and odd would hover around 50%, with some variance either way. Here’s what it *actually* outputs:

even won 6762 or 67.62% ; odd won 3238 or 32.379999999999995%

WTF? It hovered consistently around this ratio with every test! I thought at first that it was perhaps a pattern in the pseudo random number generator, but no matter what I did, it hovered strongly in favour of even.

Keep in mind this is the method most commonly recommended on tutorial sites around the net for randomising an array’s order!

I added a further test to this, to see how frequently each number ends up in the first five. Here’s the test:

var runTests = function(iterations){
  var i, j, arr, nums = [], order = [];
  for (i=0; i<10; i++) {
    nums.push({
      num: i,
      count: 0
    });
  }
  for (i=0; i<iterations; i++) {
    arr = generateRands();
    for (j=0; j<5; j++) {
      nums[arr[j]].count++;
    }
  }
  nums.sort(function(a, b){
    return a.count - b.count;
  }, true)
  for (i=0; i<10; i++) {
    order.push(nums[i].num + ' (' + nums[i].count + ')');
  }
  console.log(order);
};
runTests(10000);

The output was consistently something like this:

["9 (309)", "8 (598)", "7 (1180)", "6 (2256)", "5 (3963)",
  "4 (6170)", "3 (7926)", "2 (8817)", "1 (9386)", "0 (9395)"]

The number in parentheses represents the number of times in 10000 that the number to the left appeared in the top five. This “random” sort didn’t seem to take array members very far from home. One and zero are the only two that I could get to swap how frequently they appeared in the first five, for some reason.

What I finally realised was that the flaw was in my use of sort. Sort swaps adjacent items until it reaches the conclusion that the array is in the proper order. Each item is “less than” or “greater than” the other, and this is meant to be a consistent value. If you randomise the compare function’s output, then it will swap items, then swap them back, and finally give up on your inconsistency.

Even was coming up more often than odd because there are a greater number of even numbers from 0-4.

And now, what you probably visited this page for. A *working* array randomiser:

UPDATE: I have a much better method now in this post!

var randomSort = function(arr){
  var i, l, sortOrder = {};
  for (i=0, l=arr.length; i<l; i++) {
    sortOrder[arr[i]] = Math.random();
  }
  return arr.sort(function(a, b){
    return sortOrder[a] - sortOrder[b];
  });
};
var generateRands = function(){
  return randomSort([0,1,2,3,4,5,6,7,8,9]);
};
for (var i=0; i<5; i++) {
  runTests(10000);
}

This worked! Here’s the output:

["4 (4933)", "0 (4953)", "7 (4983)", "6 (4990)", "9 (5002)",
  "5 (5010)", "1 (5017)", "3 (5029)", "2 (5038)", "8 (5045)"]
["9 (4915)", "4 (4940)", "2 (4941)", "8 (4957)", "5 (4974)",
  "7 (5011)", "3 (5044)", "1 (5046)", "0 (5077)", "6 (5095)"]
["2 (4947)", "4 (4963)", "5 (4977)", "0 (4987)", "3 (4988)",
  "9 (5002)", "6 (5013)", "1 (5022)", "7 (5034)", "8 (5067)"]
["8 (4871)", "4 (4938)", "9 (4962)", "1 (4977)", "0 (4989)",
  "2 (4993)", "3 (5012)", "6 (5051)", "7 (5057)", "5 (5150)"]
["7 (4944)", "3 (4953)", "8 (4968)", "5 (4976)", "0 (4991)",
  "4 (5017)", "1 (5024)", "6 (5028)", "2 (5030)", "9 (5069)"]

The even/odd test above works with this new method, too.

I just wonder how many faulty array shuffling implementations are out there that don’t work!

Note: This randomSort is not perfect! Identical array values will end up adjacent to one another.