Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.