Randomize Comparator

**Trinithis** · 01-08-2008, 07:37 PM

Let's say I have the array

Code:

var a = [1, 2, 3, 4, 5, 6];

I want to randomize this through the sort function and not through a separate shuffle method.

Code:

a.sort(function(a, b) {
  // do something
});

If I'm not mistaken, the following is not a fair comparator

Code:

a.sort(function() {
  return Math.random();
});

Or at least I'm almost certain this is not truely random.

Code:

a.sort(function(a, b) {
  a = Math.random();
  b = Math.random();
  if(a > b)
    return 1;
  if(a < b)
    return -1
  return 0;
});

If anything, the comparator needs to model this form for my page because I want to use something like

Code:

function sortList(f) {
  Array.prototype.filter.call(document.getElementsByTagName("li"), (function() {
    var regex = /^\d+$/;
    return function(el) {
      return el.value && regex.test(el.value);
    };
  })()).sort(function(a, b) {
    var x = a;
    a = f(a);
    b = f(b);
    while(true) {
      try {
        if(a > b)
          return 1;
        if(a < b)
          return -1;
        return 0;
      }
      catch(e) {
        a = f(x); // IE bug
      }
    }
  }).forEach((function() {
    var i = 1;
    return function(el) {
      el.parentNode.appendChild(el);
      el.value = (i++).toString();
    };
  })());
}

sortList(function(el) {
  el.firstChild.nodeValue;
});

sortList(function(el) {
  Math.random(); // wierd results!
});

Any ideas?

**Twey** · 01-08-2008, 09:13 PM

Yes, Math.random() returns a number between 0 and 1 (and very rarely 0, obviously). In this case that means that it will almost always be above 0, which means "greater" in the context of the sorting function. Try this one:

Code:

function(a, b) { return Math.random() - 0.5; }

**Trinithis** · 01-08-2008, 09:42 PM

Hmm, that doesn't work either. Mapping the randomized values seems to work fine though:

Code:

// tested

sortList((function() {
  var m = {};
  return function(el) {
    var k = el.firstChild.nodeValue;
    if(!m[k])
      m[k] = Math.random();
    return m[k];
  };
})());

Which should be equivalent to

Code:

// untested

((function() {
  var m = {};
  return function(a, b) {
    var ka = a.firstChild.nodeValue;
    var kb = b.firstChild.nodeValue;
    if(!m[ka])
      m[ka] = Math.random();
    if(!m[kb])
      m[kb] = Math.random();
    return m[ka] - m[kb];
  };
})());

**Twey** · 01-08-2008, 09:57 PM

Code:

js> [1, 2, 3, 4, 5].sort(function() { return Math.random() - 0.5; });
2,3,1,4,5
js> [1, 2, 3, 4, 5].sort(function() { return Math.random() - 0.5; });
5,1,4,3,2
js> [1, 2, 3, 4, 5].sort(function() { return Math.random() - 0.5; });
1,4,3,2,5
js> [1, 2, 3, 4, 5].sort(function() { return Math.random() - 0.5; });
2,4,3,1,5

Define "doesn't work?" That looks pretty random to me.

**Trinithis** · 01-08-2008, 10:16 PM

I made an array with values 1-200 inclusive. In Fx, 200 likes to stay at the end. In IE, 1 likes to stay at the end. (Before I reverse the array.)

Code:

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>Test</title>
</head>
<body><div>
<script type="text/javascript">

var a = [];
for(var i = 0; i < 200; ++i)
  a[i] = i + 1;

function getRandomizer1() {
  var m = {};
  return function(a, b) {
    var ka = a;
    var kb = b;
    if(!m[ka])
      m[ka] = Math.random();
    if(!m[kb])
      m[kb] = Math.random();
    return m[ka] - m[kb];
  };
}

function getRandomizer2() {
  return function() {
    return Math.random() - 0.5;
  };
}

// probably fair
for(var i = 0; i < 10; ++i)
  document.write(a.slice().sort(getRandomizer1()).reverse() + "<br \/>");

document.write("<br \/><br \/>");

// almost certainly not fair
for(var i = 0; i < 10; ++i)
  document.write(a.slice().sort(getRandomizer2()).reverse() + "<br \/>");


</script>
</div>
</body>
</html>

**Twey** · 01-09-2008, 09:55 AM

Hm... well, with Math.random() - 0.5, you've got about-equal chances of it being higher or lower on a comparison, and almost no chance of it being equal. The element will probably be considered higher once and lower once in any sequence of two comparisons, and since it's compared to the penultimate item first, it stops if it rolls a higher and doesn't go anywhere. In the case of the last element that means that it is unlikely to move more than one space backwards. You could, if you wanted, bias it a bit:

Code:

function(a, b) { return Math.random() - 0.75; }

**jscheuer1** · 01-09-2008, 04:34 PM

Random is a strange concept, especially to the ordered mind of your typical coder, like the three of us here. Not to say we are all three of us typical coders, just that we often tend to think in an ordered manner.

Once you move over into the realm of random, you have to realize that this truly means random. One of the characteristics of randomness is that it can require an infinite number of 'tries' to get all possible recombinations of your data set. Repeats are common. I believe that the method put forward by Twey here (originally in these forums by mwinter) is sufficient and that any addition to it either reduces the truly random nature of the exercise or has no real effect upon it. This would however be notwithstanding any browser bugs or glitches.

I have found in anecdotal testing (non-statistical, observing casually*), that the method works. You can get stuck in a repeating pattern, or pattern of sorts, though for quite some time and not see certain mixes at all, then suddenly that's all you will see. Randomness can look like that, as well as like the more orderly non-repetitive output that the ordered mind, at first blush, may expect from it.

*With a process that can take infinite tries to prove itself out, no statistical analysis is really possible.

**Twey** · 01-09-2008, 05:26 PM

One of the characteristics of randomness is that it can require an infinite number of 'tries' to get all possible recombinations of your data set.

Not in a limited-size set...

you have to realize that this truly means random.

Well, actually it's pseudo-random. If you want true randomness you might want to try one of the entropy streams from random.org.

**Trinithis** · 01-09-2008, 05:41 PM

The only reason why I think

Code:

function() { return Math.random() - 0.5; }

is skeptical is because the sorting algorithm is unknown. The same part of the list can be revisited after it had been "shuffled".

Originally Posted by Wikipedia

Care needs to be taken in implementing the Knuth shuffle; even slight deviations from the correct algorithm will produce biased shuffles. For example, working your way through the pack swapping each card in turn with a random card from any part of the pack is an algorithm with n^n different possible execution paths, yet there are only n! permutations, and a counting argument based on using the pigeonhole principle on assignments of execution paths to outcomes shows that this algorithm cannot produce an unbiased shuffle, unlike the true Knuth shuffle, which has n! execution paths which match up one-to-one with the possible permutations.

Originally Posted by Wikipedia

In a computer, shuffling is equivalent to generating a random permutation of the cards. There are two basic algorithms for doing this, both popularized by Donald Knuth. The first is simply to assign a random number to each card, and then to sort the cards in order of their random numbers. This will generate a random permutation, unless two of the random numbers generated are the same. This can be eliminated either by retrying these cases, or reduced to an arbitrarily low probability by choosing a sufficiently wide range of random number choices.

The second, generally known as the Knuth shuffle or Fisher-Yates shuffle, is a linear-time algorithm (as opposed to the previous O(n log n) algorithm if using efficient sorting such as mergesort or heapsort) which involves moving through the pack from top to bottom, swapping each card in turn with another card from a random position in the part of the pack that has not yet been passed through (including itself). Providing that the random numbers are unbiased, this will always generate a random permutation.

The first algorithm looks like the one I presented above using a closure over a hash. (The getRandomizer1().)

The second looks like:

Code:

Array.prototype.shuffle = function(deep) {
  for(var i = this.length; i > 1; --i)
    this.swap(i - 1, Math.floor(Math.random() * i));
  return this;
};

Array.prototype.swap = function(i, j) {
  var t = this[i];
  this[i] = this[j]
  this[j] = t;
};

**jscheuer1** · 01-09-2008, 05:43 PM

Originally Posted by Twey

Not in a limited-size set

Practically speaking yes, you are right. In actual fact, every time you flip the coin (a set of only 2, possibly 3 if you count the possibility of the coin landing and remaining on its edge, lets say 2 here), the chances are 50/50 (1 out of 2 for each outcome) again. So, it is possible that you will get heads forever or tails forever, not too likely though.

What Trinithis is saying though is as if the browsers are using a coin with two heads. That may be, but I tend to doubt it.

As for random vs pseudo random, I never looked into it deeply enough to be able to tell if there is any practical difference for the purposes of this discussion. Is there? If so, what might that be?

Thread: Randomize Comparator

Thread Tools

Search Thread

Randomize Comparator

Bookmarks

Bookmarks

Posting Permissions