Función biyectiva

Question

Problema: todos sabemos que la simple bijection $\phi: \{0,\ldots,2^{n}-1\} \rightarrow \{0,1\}^n$ sólo por el uso de los números binarios.

Sin embargo, hay un bijection $\psi: \{0,\ldots,2^{n}-1\} \rightarrow \{0,1\}^n$ tal que $|\psi(i+1)-\psi(i)|^2 \leq 2$ todos los $i \in \{0,\ldots,2^{n}-2\}$? Es decir, un bijection donde nunca cambiar más de $2$ "bits"?

Mi planteamiento: Después de pensar un poco tengo la idea de que se puede probar esto mediante la clasificación de todos los $\{0,1\}^n$ tuplas por la cantidad de unidades que se producen y, a continuación, utilice esta opción para definir su bijection, usted sólo tiene que mostrar que no puede ser que hay "saltos" en la lista ordenada de más de 2 bits cambiados. Sin embargo, también estoy interesado en una definición concreta que podría ser a través de algoritmos implementados y no sólo de una aproximación teórica, es decir, usted necesita saber que bits para cambiar al incremento de su número.

Nota: $\{0,1\}^n$ significa que una tupla de longitud $n$ entradas $0$ o $1$.

Answer 1

Lo que quieres es un código gris, que de hecho sólo cambia un bit a la vez.

Answer 2

Hay muchas soluciones, sobre todo si permite cambiar 2 bits en lugar de uno en uno. Pero de hecho gris código es la solución más simple. Tomar la representación binaria, luego cada poco excepto el primero, agregar a él (modulo 2) la broca a la izquierda (su valor antes de esta modificación, por lo tanto trabajar de derecha a izquierda si hacerlo secuencialmente, una computadora puede hacerlo en paralelo tomando la cantidad binaria, y tomando el XOR bit a bit con el mismo uno lugar cambiado de puesto número a la derecha).

Answer 3

se trata de código gris (que tiene $|\psi(i+1 \mod 2^n)-\psi(i)|^2 = 1$ para $0 \leq i \lt 2^n$)

y hay una construcción prueba aquí

$n=1$ es trivial: $\{(1),(0)\}$

$n+1$ concatenan el código $n$ (cada uno el prefijo $0$) con su revés (con cada prefijo con $1$)