Is there a generalization for the Cantor Pairing function to (ordered) triples and ultimately to (ordered) n-tuples? It's however important that the there exists an inverse function: computing z from (w, x, y) and also computing w, x and y from z. In other words:
- project(w, x, y) = z
- unproject(z) = (w, x, y)
Thinking about it in terms of a three-/n-dimensional coordinate system it should be possible to generalize from ordered pairs to at least ordered triples and most probably also to ordered n-tuples. Is anyone aware of any resources (papers, books, websites...) where such a function is described?
$\endgroup$ 73 Answers
$\begingroup$Let $\varphi_2:\omega\times\omega\to\omega$ be any explicit pairing function (e.g., the Cantor pairing function), and let $\psi_0:\omega\to\omega$ and $\psi_1:\omega\to\omega$ be explicit functions such that $\psi_i\big(\varphi_2(n_0,n_1)\big)=n_i$ for $i=0,1$. Define $\varphi_k$ for $k\ge 2$ recursively by letting
$$\varphi_{k+1}:\omega^{k+1}\to\omega:\langle n_0,\ldots,n_k\rangle\mapsto\varphi_2\big(n_0,\varphi_k(n_1,\ldots,n_k)\big)$$
for each $k\ge 2$. Clearly each $\varphi_k$ can be computed simply by iterating $\varphi_2$ $k$ times on suitable arguments.
For each $k\ge 2$ and $i<k$ there is a function $\psi_i^{(k)}:\omega\to\omega$ such that
$$\psi_i^{(k)}\big(\varphi_k(n_0,\ldots,n_{k-1})\big)=n_k$$
for $i<k$. These are easily described in terms of $\psi_0$ and $\psi_1$:
$$\psi_i^{(k)}(n)=\big(\psi_0\circ\psi_1^i\big)(n)$$
for each $n\in\omega$, where $\psi_1^i=\underbrace{\psi_1\circ\ldots\circ\psi_1}_{i\text{ copies}}$. (Of course $\psi_1^0$ is the identity function.)
Thus, given code for $\varphi_2$, $\psi_0$, and $\psi_1$, you can easily write code for $\varphi_k$ for all $k\ge 2$, and for $\psi_i^{(i)}$ for all $k\ge 2$ and $i<k$. There’s no need to work out the messy algebra.
$\endgroup$ 1 $\begingroup$The solution, in retrospect, seems "obvious" but I was having a hard time grasping it until I understood an example.
The pairing function takes two numbers as input and returns one: $ \mathbb{N} \times \mathbb{N} \to \mathbb{N}$
So what do you do with, say, a 3-tuple? Pick 2 items, use the pairing function to turn that into 1. Now use the pairing function again to turn your two remaining items into 1.
More formally
In computability we are often forced to resort to dovetailing along 3, 4 or even more dimensions. We can define "higher pairing" functions recursively, by using two-dimensional pairing functions as a base case. Formally, we define the function $ <.,.,...,.>_n$, which pairs $n$ natural numbers recursively as follows:
$<>_0 = 0$ and $<x>_1 = x$,
$<x,y>_2 = <x,y>$,
$<x_1, ..., x_{n-1}, x_n>_n = <x_1, ..., <x_{n-1}, x_n>>_{n-1}$.
4-tuple example ( $ \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N} \times \mathbb{N} \to \mathbb{N} \times \mathbb{N} \to \mathbb{N} $ )
$$ a,b,c,d $$$$ a,b,(c,d) $$$$ a,b,e $$$$ a,(b,e) $$$$ a,f $$$$ (a,f) $$$$ g $$
$\endgroup$ $\begingroup$Ok, I think I got it. Your idea is to create recursive functions for both pair and unpair and simply "assemble" the results instead of computing them with an algebraic formula. Of course this works due to the nature of pairing function. If I have time I will add the code in here.
Just one more question: Assuming I actually knew the pairing function for, let's say, triples (or n-tuples). In terms of processing speed on a regular computer, do you think it would be faster than a recursive solution? I assume it would be, because recursion requires to repeatedly create an internal stack for each recursive function call, whereas a mathematical function would just be computed once. So, if it's really about getting the most out of your processor, it would be worth trying to find the algebraic solution to this problem.
$\endgroup$ 1
