A pairing function is a function that reversibly maps onto , where denotes nonnegative integers. Pairing functions arise naturally in the demonstration that the cardinalities of the rationals and the nonnegative integers are the same, i.e., , where 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.
5 | 15 | 20 | 26 | 33 | 41 | |
4 | 10 | 14 | 19 | 25 | 32 | |
3 | 6 | 9 | 13 | 18 | 24 | |
2 | 3 | 5 | 8 | 12 | 17 | |
1 | 1 | 2 | 4 | 7 | 11 | |
1 | 2 | 3 | 4 | 5 |
Let
(1)
|
then Hopcroft and Ullman (1979, p. 169) define the pairing function
(2)
| |||
(3)
|
illustrated in the table above, where . The inverse may computed from
(4)
| |||
(5)
| |||
(6)
| |||
(7)
|
where is the floor function.
5 | 15 | 22 | 30 | 39 | 49 | 60 | |
4 | 10 | 16 | 23 | 31 | 40 | 50 | |
3 | 6 | 11 | 17 | 24 | 32 | 41 | |
2 | 3 | 7 | 12 | 18 | 25 | 33 | |
1 | 1 | 4 | 8 | 13 | 19 | 26 | |
0 | 0 | 2 | 5 | 9 | 14 | 20 | |
0 | 1 | 2 | 3 | 4 | 5 |
The Hopcroft-Ullman function can be reparameterized so that and are in rather than . This function is known as the Cantor function and is given by
(8)
|
illustrated in the table above. Its inverse is then given by
(9)
| |||
(10)
| |||
(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 onto reversibly (Stein 1999, pp. 448-452).
11 | 20 | 24 | 33 | 41 | |
10 | 12 | 19 | 25 | 32 | |
4 | 9 | 13 | 18 | 26 | |
3 | 5 | 8 | 14 | 17 | |
1 | 2 | 6 | 7 | 15 |
17 | 18 | 19 | 20 | 21 | |
16 | 15 | 14 | 13 | 22 | |
5 | 6 | 7 | 12 | 23 | |
4 | 3 | 8 | 11 | 24 | |
1 | 2 | 9 | 10 | 25 |
Stein (1999) proposed two boustrophedonic ("ox-plowing") variants, shown above, although without giving explicit formulas.
7 | 42 | 43 | 46 | 47 | 58 | 59 | 62 | 63 | |
6 | 40 | 41 | 44 | 45 | 56 | 57 | 60 | 61 | |
5 | 34 | 35 | 38 | 39 | 50 | 51 | 54 | 55 | |
4 | 32 | 33 | 36 | 37 | 48 | 49 | 52 | 53 | |
3 | 10 | 11 | 14 | 15 | 26 | 27 | 30 | 31 | |
2 | 8 | 9 | 12 | 13 | 24 | 25 | 28 | 29 | |
1 | 2 | 3 | 6 | 7 | 18 | 19 | 22 | 23 | |
0 | 0 | 1 | 4 | 5 | 16 | 17 | 20 | 21 | |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
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
(12)
|
where (and ) are the least significant bit of (or ), 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 can be defined as or , but should be defined as to minimize the size of the number thus produced. The general scheme is then
(13)
| |||
(14)
| |||
(15)
| |||
(16)
| |||
(17)
|
and so on.