 | Three different bijections or pairing functions between N and N2 (including Cantor polynomials)
Bijection_Pairing_N_N2(index_In,flag_Pair) provides three different explicit bijections between [0,...,K] and some consistently growing (Cantor or triangle, Elegant or square, Power-Of-Two-Odd or POTO for 2-adic integer decomposition) subset of N2. It allows different strategies to wander across a set of two-dimensional integer coordinates.
The most famous pairing functions between N and N2 are Cantor polynomials:
= ((x+y)^2+x+3y)/2 or = ((x+y)^2+3x+y)/2).
Whether they are the only bijective polynomials (between N and N2) 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+floor((x+1)/2))^2.
It is given by: flag_Pair = 'Elegant' or 'e'.
'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:
= 2^x*(2*y-1) - 1.
It is given by: flag_Pair = 'Elegant' or 'e'.
Without 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.
|