You're reading: cp's mathem-o-blog, Uncategorized

The permutation clock

52 playing cards arranged in a grid

I recently had an idea: map the Unix time (seconds since 1st January 1970) to shufflings of a deck of cards. Each second would correspond to a different ordering of the 52 cards.

I wanted to think about how mind-bogglingly huge $52!$ is: $52!$ seconds is more than $2 \times 10^{60}$ years. So even if you spent your entire life watching this thing, you’d leave this world having seen basically none of the possible permutations. Happily, Wikipedia reckons that the heat death of the universe will happen in about $10^{100}$ years, so there’s plenty of time for me to enact my plan.

But the really mind-boggling part is that the mapping between the numbers 1 to 52! and the orderings of a deck of cards isn’t very complicated: given a number, I can tell you which ordering it corresponds to in almost no time at all.

I say the mapping, but there are 52!! (a number ending in 20,164,543,792,735,969,642,915,159,214,100,941,743,822,376,360,220,819,455,999,999,999,951 zeros) choices of mapping. I wanted a good one: to go from one permutation to the next you swap a pair of adjacent cards.

Someone’s already come up with a way of doing this: Heap’s algorithm. It solves the problem of generating all the permutations of $n$ objects, iteratively: starting from the ordering $1, 2, \ldots, n$, it tells you which pair of cards to swap at each stage. I wanted to do something slightly different: given a number – a step in the algorithm – I want to quickly know what the corresponding permutation is without performing all the swaps individually.

The idea behind Heap’s algorithm is this: you can get all the permutations of the numbers $1$ to $n$ by inserting the number $n$ in all possible positions in the permutations of the numbers $1$ to $n-1$.

It’s an induction: suppose you’ve got all the permutations of $1$ to $n-1$ in order so that adjacent permutations differ by a single swap. Then you “sweep” the number $n$ from the rightmost position to the leftmost, make the swap to move to the next permutation of the remaining numbers, then sweep back to the right again. You do this back and forth until you’ve worked through all the permutations.

Let $\pi_n(i)$ be the $i$th permutation of the numbers $1$ to $n$ produced by Heap’s algorithm.

It turned out to be quite easy to work out what $\pi_n(i)$ is: you can divide the list into groups of $n$, with each group corresponding to $\pi_{n-1}(\lfloor i/n \rfloor)$ with $n$ inserted in each of the $n$ possible positions. The direction that $n$ travels in is determined by whether $\lfloor i/n \rfloor$ is odd or even. So you place $n$ first, then $n-1$, and so on until $1$.

My JavaScript function to map integers to permutations looks like this:

function int_to_permutation(i,n) {
  const out = [];
  // place each of the numbers 1 to n, working backwards from n
  for(let j=n;j>0;j--) {
    // write i as q*j + m;
    const m = i % j;
    const q = (i-m)/j;

    // find out where the number j should go - it's the m^th non-empty place from whichever end we're starting at
    let x = 0;
    let s = 0;
    // if q is odd, start from the left, otherwise start from the right
    const p = (x,s) => q%2 ? x+s : n-1-x-s;
    for(;x<=m;) {
      if(out[p(x,s)]!==undefined) {
        s += 1;
      } else {
        x += 1;
      }
    }
    const place = p(x-1,s);
    out[p(x-1,s)] = j;
    i = q;
  }
  return out;
}

So here’s a pack of 52 playing cards, working through every possible permutation:

Once I’d implemented this, I thought about how to present it. I realised that once I’d seen how ridiculously big 52! is, I wanted to know how many cards I could feasibly see all the permutations of. So I added a countdown underneath the cards showing how long is left.

A set of 13 cards will take 198 years, while a set of 10 will only take 42 days. (It’s one of those neat coincidences that 10! seconds is exactly six weeks) Factorials really do grow quickly! Right now, the Unix time is 1598629111, which is considerably bigger than $12!$ (16 years) but considerably smaller than $13!$ (197 years).

I made a second version of the clock, using emoji instead of playing cards, and starting from when you open the page instead of in 1970. You might want to use it as a sand timer: $5!$ seconds is exactly two minutes.

Here’s the version with 10 cards. I’m fairly sure it won’t have finished by the time you’ve read this far:

Leave a Reply

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Google+