Mœud

Pairing functions are used to reversibly map a pair of number onto a single number—think of a number-theoretical version of std::pair. Cantor was the first (or so I think) to propose one such function. His goal wasn’t data compression but to show that there are as many rationals as natural numbers.

Cantor’s function associates pairs (i,j) with a single number:

…but that’s not the only way of doing this. A much more fun—and spatially coherent—is the boustrophedonic pairing function.

Boustrophedonic (litt. “ox-turning”, as an image of how oxen plow fields, revering course at the end of a line) will associate pairs in a spatially coherent manner:

Numerically,

Of course, there’s the fun in finding the function, but there are also applications. For example, one could use this order to scan an (arbitrarily large) matrix before/for quantization.

*
* *

Let’s define:

\displaystyle \Delta(x)=\frac{1}{2}x(x+1).

with its rounded-down inverse

\displaystyle \Delta^{-1}(x)=\left\lfloor\sqrt{2x+\frac{1}{4}}-\frac{1}{2} \right\rfloor.

Now, the hard part is managing the reversals. Diagonal direction depends on the diagonal’s number. If we pair i and j, then this combination will lie on diagonal i+j. If the diagonal number is even, it winds north-east, if it’s odd, it winds south-west. It it winds south-west, we count backwards—relative to Cantor’s function—from the next diagonal.

\displaystyle  b(i,j)=  \begin{cases}  \Delta(i+j)+j&\mathrm{if~}i+j\mathrm{~is~even}\\  \Delta(i+j+1)-j-1&\mathrm{~otherwise}  \end{cases}  .

The function’s inverse must also deal with diagonal reversal:

\displaystyle  b^{-1}(n)=  \begin{cases}  (r,d-r)&\mathrm{if~}d\mathrm{~is~even}\\  (d-r,r)&\mathrm{otherwise}  \end{cases}  .

where

d=\Delta^{-1}(n),

r=n-\Delta(n).

*
* *

The Mathematica code is quite simple:

\[CapitalDelta][x_] := 1/2 x (x + 1)

i\[CapitalDelta][x_] := Floor[Sqrt[2 x + 1/4] - 1/2]

b[i_, j_] := 
 If[EvenQ[i + j], \[CapitalDelta][i + j] + 
   j, \[CapitalDelta][i + j + 1] - j - 1]

iB[n_] := Module[{d = i\[CapitalDelta][n], r},
  r = n - \[CapitalDelta][d];
   If[EvenQ[d],
   {d - r, r},
   {r, d - r}
   ]
  ]

One Response to Mœud

  1. […] [1] Steven Pigeon,  Mœud [2] Wikipedia, Pairing function [3] […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: