Mon 01 March 2010 | -- (permalink)

So the EU ordered Microsoft to give European Windows users a randomized browser-picking screen instead of just railroading everyone into IE by default. Then the site DSL.sk did some digging and found that the ballot wasn't really random at all. Naturally this was perfect ammunition for the anti-Microsoft conspiracy theorists, but a neat post from Rob Weir shows that the non-randomness of the ballot is due more to negligence than mendacity.

What got my geeky heart all aflutter though was learning the right way to randomly shuffle a list of things. Rob links to a Wikipedia article on the Fischer Yates shuffle. A lot of gibberish and formal algorithmic notation later, I still didn't really understand how the shuffle worked. Then they got down to the code examples:

from random import randrange

def shuffle(items):
    n = len(items)
    while n > 1:
        k = randrange(n)  # 0..n-1
        n = n - 1
        items[k], items[n] = items[n], items[k]
    return

Perhaps the highest praise I've heard about Python is that it is "executable pseudocode." I'll take that over a formal college textbook notation any day. It makes me wonder why people bother with things like this:

To shuffle an array a of m elements:
   initialize a such that ∀ i . a[i] ← i
   for n from m - 1 downto 1 do
         j ← random (0 .. n)
         exchange a[j] and a[n]