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. Cantor’s enumeration of N^2 revisited – TheDestructionOfThirstByWater says:

[…]  Steven Pigeon,  Mœud  Wikipedia, Pairing function  […]