TOPICS
Search

Pairing Function


A pairing function is a function that reversibly maps Z^*×Z^* onto Z^*, where Z^*={0,1,2,...} denotes nonnegative integers. Pairing functions arise naturally in the demonstration that the cardinalities of the rationals Q and the nonnegative integers Z^* are the same, i.e., |Q|=|Z^*|=aleph_0, where aleph_0 is known as aleph-0, originally due to Georg Cantor. Pairing functions also arise in coding problems, where a vector of integer values is to be folded onto a single integer value reversibly.

||||||...
51520263341...
41014192532...
369131824...
23581217...
1124711...
i/j12345...

Let

 Delta(x)=1/2x(x+1),
(1)

then Hopcroft and Ullman (1979, p. 169) define the pairing function

<i,j>=Delta(i+j-2)+i
(2)
=1/2(i+j-2)(i+j-1)+i,
(3)

illustrated in the table above, where i,j in {1,2,3,...}. The inverse may computed from

h=<i,j>
(4)
c=|_sqrt(2h)-1/2_|
(5)
i=h-Delta(c)
(6)
j=c-i+2,
(7)

where |_x_| is the floor function.

|||||||...
5152230394960...
4101623314050...
361117243241...
23712182533...
1148131926...
002591420...
i/j012345...

The Hopcroft-Ullman function can be reparameterized so that i and j are in {0,1,2,...} rather than {1,2,3,...}. This function is known as the Cantor function and is given by

 <i,j>_(Cantor)=<i+1,j+1>_(HU)-1,
(8)

illustrated in the table above. Its inverse is then given by

k=<i,j>_(Cantor)+1
(9)
{i^',j^'}=<k>_(HU)^(-1)
(10)
{i,j}={i^'-1,j^'-1}.
(11)

A theorem due to Fueter and Pólya states that Cantor's pairing function and Hopcroft and Ullman's variant are the only quadratic functions with real-valued coefficients that maps Z^*×Z^* onto Z^* reversibly (Stein 1999, pp. 448-452).

|||||...
1120243341...
1012192532...
49131826...
3581417...
126715...
|||||...
1718192021...
1615141322...
5671223...
4381124...
1291025...

Stein (1999) proposed two boustrophedonic ("ox-plowing") variants, shown above, although without giving explicit formulas.

|||||||||...
74243464758596263...
64041444556576061...
53435383950515455...
43233363748495253...
31011141526273031...
289121324252829...
1236718192223...
0014516172021...
i/j01234567...

There are also other ways of defining pairing functions. For example, Pigeon (2001, p. 115) proposed a pairing function based on bit interleaving. This "bitwise" pairing function, illustrated above, is defined

 <i,j>_P={_|_   if i=j=0; <|_i/2_|,|_j/2_|>_(SP):i_0:j_0   otherwise,
(12)

where i_0 (and j_0) are the least significant bit of i (or j), : is a concatenation operator, and the symbol _|_ is the empty bit string

To pair more than two numbers, pairings of pairings can be used. For example <i,j,k> can be defined as <i,<j,k>> or <<i,j>,k>, but <i,j,k,l> should be defined as <<i,j>,<k,l>> to minimize the size of the number thus produced. The general scheme is then

<a,b,c>=<a,<b,c>>
(13)
<a,b,c,d>=<<a,b>,<c,d>>
(14)
<a,b,c,d,e>=<<a,b>,<c,<d,e>>>
(15)
<a,b,c,d,e,f>=<<a,b>,<<c,d>,<e,f>>>
(16)
<a,b,c,d,e,f,g>=<<a,<b,c>>,<<d,e>,<f,g>>>,
(17)

and so on.


See also

Folding Function

This entry contributed by Steven Pigeon

Explore with Wolfram|Alpha

References

Hopcroft, J. E. and Ullman, J. D. Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison Wesley, 1979.Pigeon, P. Contributions à la compression de données. Ph.D. thesis. Montreal, Université de Montréal, 2001.Stein, S. K. Mathematics: The Man-Made Universe. New York: McGraw-Hill, 1999.

Referenced on Wolfram|Alpha

Pairing Function

Cite this as:

Pigeon, Steven. "Pairing Function." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/PairingFunction.html

Subject classifications