File Exchange

image thumbnail

Three different bijections or pairing functions between N and N^2 (including Cantor polynomials)

version (3.44 KB) by Laurent Duval
Pairing functions: encoding of two natural numbers into a single natural number (and vice-versa)


Updated 14 Nov 2013

View License

Bijection_Pairing_N_N2(index_In,flag_Pair) provides three different explicit bijections between [0,...,K] and some consistently growing subset of N^2 (according to three modes: Cantor or triangle, Elegant or square, Power-Of-Two-Odd or POTO for the 2-adic integer decomposition). It allows different strategies to wander across a set of two-dimensional integer coordinates. Such bijections are called "pairing functions", "one-to-one correspondences between lattice points", "diagonal functions".

The most famous pairing functions between N and N^2 are Cantor polynomials:
<x,y> = ((x+y)^2+x+3y)/2 or <x,y> = ((x+y)^2+3x+y)/2).

The Cantor enumeration pattern follows, for instance:
0 1 3 6 10 15
2 4 7 11 16
5 8 12 17
9 13 18
14 19

Whether they are the only bijective polynomials (between N and N^2) remains an open question. They parse the positive quadrant along parallel, anti-diagonal lines, starting from the (0,0) origin. The indices increase as growing triangles, following an l_1 norm, i.e. the sum of x and y is piece-wise constant and non-decreasing. It is given by: flag_Pair = 'Cantor' or 'c'.

A second pairing function grows in concentric squares. It elegantly mimics a max or l_infinity norm, with <x,y> = x+(y+floor((x+1)/2))^2.

It is given by: flag_Pair = 'Elegant' or 'e'.

The Elegant enumeration pattern follows, for instance:
0 2 6 12
1 3 7 13
4 5 8 14
9 10 11 15

'Cantor' and 'Elegant' pairing are relatively symmetric around the main diagonal.

The third and last one (POTO pairing) is more asymmetric. It can be used when one index should grow quicker than the other (roughly hyperbolic). It is related to the 2-adic representation, or the decomposition of an integer into the product of a power of two and an odd number (Power-Of-Two-Odd). It corresponds to:
<x,y> = 2^x*(2*y-1) - 1.

It is given by: flag_Pair = 'Elegant' or 'e'.

The POTO enumeration pattern follows, for instance:
0 1 3 7 15
2 5 11
4 9
6 13
8 17

Without an output argument, the code displays the competition between 'Cantor', 'Elegant' and 'POTO', up to the first integer both triangular and square: 36 (not 42, to my infinite sadness).

The bijection order is given by the dimension (1 or 2) of the input index.

A few references are provided for implementing pairing functions in higher dimensions.

Comments and Ratings (0)


Added initial patterns for the three diagonal functions

MATLAB Release Compatibility
Created with R2011b
Compatible with any release
Platform Compatibility
Windows macOS Linux