2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, this works great. Never really thought of it like that, interesting perspective $\endgroup$ – V9801 Jul 27 '13 at 23:42
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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