= Cantor pairing function
{c}
{title2=$\pi(x,y)=\frac{(x+y)(x+y+1)}2+y$}
The Cantor pairing function is an explicit <bijection> between $\mathbb N^2$ and $\mathbb N$, with the <natural numbers> numbered from zero:
$$
\pi(x,y)=\frac{(x+y)(x+y+1)}2+y.
$$
If $d=x+y$, there are $1+2+\cdots+d=d(d+1)/2$ pairs on earlier diagonals, and the pair $(x,y)$ is at offset $y$ along diagonal $d$. The formula therefore gives exactly the enumeration above. For example, $\pi(2,3)=5\cdot6/2+3=18$.
For the inverse at an index $k$, find the unique $d$ satisfying $d(d+1)/2\leq k<(d+1)(d+2)/2$, then put $y=k-d(d+1)/2$ and $x=d-y$. At $k=18$, these are $d=5$, $y=3$, and $x=2$. Thus both the encoding and decoding are explicit. The <bijection> is useful for assigning a single <natural number> to a pair of indices, and iterating it does the same for fixed-length <tuples>.
Back to article page
