# One-to-one functions between vectors of integers and integers, with easily computable inverses

I'm trying to find functions that fit certain criteria. I'm not sure if such functions even exist. The function I'm trying to find would take vectors of arbitrary integers for the input and would output an integer. It is one-to-one. Both the function and its inverse should be easy to compute with a computer. The inverse should output the original vector, with the elements in the same indices.

Just something I've been trying to think of. Thanks for all your help.

-
There were some questions about Cantor pairing function at this site. (Some other pairing functions might be interesting for you, too.) Here are a few of them: Bijection between $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$, Proving the Cantor Pairing Function Bijective or Inverting the Cantor pairing function. – Martin Sleziak Jul 31 '13 at 11:14
I've added (elementary-set-theory) tag. It seems suitable to me, since the question is about bijections. I've also added (algorithms) tag, since you want the function to be easily computed. – Martin Sleziak Jul 31 '13 at 11:15

What you need is a bijection $\alpha : \mathbb{N}^2 \to \mathbb{N}$ which is easy to compute in both forward and backward directions. For example,

\begin{align} \mathbb{N}^2 \ni (m,n) & \quad\stackrel{\alpha}{\longrightarrow}\quad \frac{(m+n)(m+n+1)}{2} + m \in \mathbb{N}\\ \mathbb{N} \ni N & \quad\stackrel{\alpha^{-1}}{\longrightarrow}\quad (N - \frac{u(u+1)}{2},\frac{u(u+3)}{2} - N) \in \mathbb{N}^2, \end{align} where $u = \lfloor\sqrt{2N+\frac14}-\frac12\rfloor$.

Once you have such a bijection, then given any $k \ge 1$ natural numbers $x_1, x_2, \ldots x_k$, you can encode it into a single natural number as:

$$( x_1, \ldots, x_k ) \mapsto \alpha(k,\alpha(x_1,\alpha(\ldots,\alpha( x_{k-1}, x_{k} )))$$

To decode this number, you apply $\alpha^{-1}$ once to get $k$ and $\alpha(x_1,\alpha(\ldots,\alpha( x_{k-1}, x_{k} )))$. Knowing $k$, you know how many times you need to apply $\alpha^{-1}$ to the second piece and get all the $x_k$ back.

Other cases like:

• encoding signed instead of unsigned integers
• allow encoding of zero number of integers

can be handled in similar manner.

-
Thanks, this works great. Never really thought of it like that, interesting perspective – Vishnu Jul 27 '13 at 23:42

Try a scheme like the enumeration of rational numbers. Here a 3-dimensional example: \begin{align} 0 &\mapsto (0,0,0) \\ 1 &\mapsto (1,0,0) \\ 2 &\mapsto (0,1,0) \\ 3 &\mapsto (0,0,1) \\ 4 &\mapsto (2,0,0) \\ 5 &\mapsto (1,1,0) \\ 6 &\mapsto (1,0,1) \\ 7 &\mapsto (0,2,0) \\ 8 &\mapsto (0,1,1) \\ 9 & \mapsto (0,0,2) \end{align}

Then all vectors with entries summing up to 3, 4, etc.

If you allow for negative entries, first sum up all with sum of absolute values equa 1, then 2, etc.

-