An Elegant Pairing Function

Matthew Szudzik

Wolfram Research, Inc.

We all know that every point on a surface can be described by a pair of coordinates, but can every point on a surface be described by only one coordinate?  Perhaps you say, "No, that is not possible—a surface is two dimensional, so you need two coordinates."

Well, if you would have said that, then you would be wrong.  It is possible to describe the points on a surface with only one coordinate, and a method for doing this was first described by Georg Cantor in 1878.

Definition

A pairing function on a set A associates each pair of members from A with a single member of A, so that any two distinct pairs are associated with two distinct members.

Cantor's Pairing Function

Here is a classic example of a pairing function (see page 1127 of A New Kind Of Science).  When x and y are non-negative integers, Pair[x, y] outputs a single non-negative integer that is uniquely associated with that pair.

Pair[x_, y_] := (((x^2) + 3  x + 2  x y + y + (y^2))/2)

It assigns consecutive numbers to points along diagonals in the plane .

The inverse function Unpair[z] outputs the pair associated with each non-negative integer z.

Unpair[
        z_] := 
With[{i  =  ⌊((-1  +  (Sqrt[1  +  8 z]))/2)⌋},  { 
          z - ((i (1 + i))/2), ((i (3 + i))/2) - z}]

Example: SK-Combinator Expressions

SK-combinator expressions are expressions built from the symbols s and k using the operation of function application.  For example,

s[k[s]][k]s[k[s]][k]

is an SK-combinator expression.  SK-combinators are an important class of computational system.  See page 1121 of A New Kind Of Science for background information regarding SK-combinators.

Pairing functions can be used to enumerate the SK-combinator expressions.  NthCombinator[n] outputs the nth SK-combinator expression.

NthCombinator[0] := k
NthCombinator[1] := s
NthCombinator[
        n_] := #1[#2] & @@  NthCombinator  /@  
          Unpair[n - 2]

The first 1000 SK-combinator expressions are the following.

Table[{n, NthCombinator[n]}, {n, 0, 1000}]  //  TableForm

Note that the expressions are in an inconvenient order.  For example, the simple expression s[s][s][s] is number 741 in the list.

A more elegant pairing function

When x and y are non-negative integers, ElegantPair[x, y] outputs a single non-negative integer that is uniquely associated with that pair.

ElegantPair[x_, y_]:=(Piecewise[{{(y^2) + x, x ≠ Max[x, y]}, {(x^2) + x + y, x == Max[x, y]}}])

The inverse function ElegantUnpair[z] outputs the pair associated with each non-negative integer z.

ElegantUnpair[z_]:=(Piecewise[{{{z - ⌊(Sqrt[z])⌋^2, ⌊(Sqrt[z])⌋}, z - ⌊(Sqrt[z])⌋^2 < ⌊(Sqrt[z])⌋}, {{⌊(Sqrt[z])⌋, 
                z - ⌊(Sqrt[z])⌋^2 - ⌊(Sqrt[z])⌋}, z - ⌊(Sqrt[z])⌋^2 ≥ ⌊(Sqrt[z])⌋}}])

This pairing function assigns consecutive numbers to points along the edges of squares.

The elegant property of this pairing function is that it orders the SK-combinator expressions, and many other sorts of expressions, by depth.

NthElegantCombinator[0] := k
NthElegantCombinator[1] := s
NthElegantCombinator[
        n_] := #1[#2] & @@  NthElegantCombinator  /@  
          ElegantUnpair[n - 2]

Table[{n, NthElegantCombinator[n], 
          Depth[NthElegantCombinator[n] //. a_[b_] -> {a, b}]}, {n, 0, 
          50}]  // TableForm

The pairing function can be understood as an ordering of the points in the plane.  Given two points {u, v} and {x, y}, the point {u, v} occurs at or before {x, y} if and only if PairOrderedQ[{u, v}, {x, y}] is True.

PairOrderedQ[{u_, v_}, {x_, y_}] := 
Max[u, v] < 
          Max[x, y]  ∨ (Max[u, v] == Max[x, y] ∧  
            OrderedQ[{{u, v}, {x, y}}])

This ordering uniquely defines the pairing function, and it has the advantage that it can easily be generalized to higher dimensions.  For example, a tripling function (a function that uniquely associates a single non-negative integer with each triple of non-negative integers) is uniquely defined by the ordering TripleOrderedQ[{u, v, w}, {x, y, z}].

TripleOrderedQ[{u_, v_, w_}, {x_, y_, 
          z_}] := 
Max[u, v, w] < 
          Max[x, y, z]  ∨ (Max[u, v, w] == Max[x, y, z] ∧  
            OrderedQ[{{u, v, w}, {x, y, z}}])

References

Georg Cantor, Ein beitrag zur mannigfaltigkeitslehre, Journal für die reine und angewandte Mathematik 84 (1878), 242–258.

Stephen Wolfram, A new kind of science, Wolfram Media, 2002.