Funciones uno a uno entre vectores de enteros y enteros, con inversos fácilmente computables

Question

Intento encontrar funciones que se ajusten a ciertos criterios. No estoy seguro de que existan tales funciones. La función que estoy tratando de encontrar tomaría vectores de enteros arbitrarios para la entrada y la salida de un número entero. Es uno-a-uno. Tanto la función como su inversa deberían ser fáciles de calcular con un ordenador. La inversa debe dar como resultado el vector original, con los elementos en los mismos índices.

Sólo algo que he estado intentando pensar. Gracias por toda su ayuda.

Answer 1

Lo que necesitas es una biyección $\alpha : \mathbb{N}^2 \to \mathbb{N}$ que es fácil de calcular tanto hacia delante como hacia atrás. Por ejemplo,

$$\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}$$ donde $u = \lfloor\sqrt{2N+\frac14}-\frac12\rfloor$ .

Una vez que se tiene dicha biyección, dada cualquier $k \ge 1$ números naturales $x_1, x_2, \ldots x_k$ se puede codificar en un único número natural como:

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

Para descodificar este número, se aplica $\alpha^{-1}$ una vez para obtener $k$ y $\alpha(x_1,\alpha(\ldots,\alpha( x_{k-1}, x_{k} )))$ . Conocer $k$ , ya sabes cuántas veces tienes que aplicar $\alpha^{-1}$ a la segunda pieza y obtener todos los $x_k$ atrás.

Otros casos como:

• codificación de enteros con signo en lugar de sin signo
• permitir la codificación de un número cero de enteros

pueden tratarse de forma similar.

Answer 2

Prueba un esquema como la enumeración de números racionales. Aquí un ejemplo tridimensional: \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}

Entonces todos los vectores con entradas que suman 3, 4, etc.

Si permite entradas negativas, primero sume todo con la suma de valores absolutos igual a 1, luego 2, etc.