Podemos pensar tanto en los problemas mediante el llenado de un número de la izquierda y progessively "tomar elección de distancia". Voy a detalle de la construcción de los números que comiencen con un $0$ (tanto de tipo 1 y tipo 2), pero el algoritmo puede ser duplicado para los números con un inicial de $1$.
Voy a llamar a los números con una cantidad igual de ceros y unos "equilibrado" y los números de otro tipo de "salir". (La suma de $\sum_{i=0}^k (2a_i-1)$ comienza $0$, entonces se va y nunca regresa para un crecimiento $k$.)
La asignación de "equilibrado" números "salir" de los números, primero algunos ejemplos:
$$001011 → 001001; 011100 → 000110$$
$$000111 → 001010; 010101 → 000000$$
So how does this construction work? As mentioned, the result is build by emitting digit after digit while the input is slowly consumed. This may happen at different speeds. During this we will need to remember one core variable: $$δ = \text{the amount of consumed zeroes - the amount of consumed ones}$$
La cantidad restante de entrada de $ρ$ también es importante. En particular, cuando se $ρ=δ$ sostiene, todos los dígitos restantes de la entrada ya están definidos! La entrada no nos dice nada más. En este punto ya deberíamos haber construido el resultado final. Finalmente, queremos saber
$$s = \text{amount of emited zeroes} - \text{amount of emited ones.}$$
This is important, as we must always insure that $s \geq 1$, and when $s = 1$ we are forced to emit a $0$.
Aquí es el algoritmo:
Input | is δ > 0? | What to emit
0 | NO | 0
0 | YES | 1
1 | NO | 1
1 | YES | 0
Aquí está un ejemplo de ejecución en 001011:
Remaining input | read | δ | s | ρ | emited output
001011 | -- | 0 | 0 | 6 | nothing
01011 | 0 | 1 | 1 | 5 | 0
01011 | -- | 1 | 2 | 5 | 00 // because s=1 forces us
1011 | 0 | 2 | 1 | 4 | 001
1011 | -- | 2 | 2 | 4 | 0010 // forced by s=1
011 | 1 | 1 | 3 | 3 | 00100
11 | 0 | 2 | 2 | 2 | 001001 // now δ=ρ, terminate
¿Cuál es la Idea detrás de todo esto?
Este bijection es acerca de mannaging el resto de opción a la izquierda. Para equilibrado de los números, teniendo futura elección de distancia significa escoger un número que ya está más numerosos. Para salir de números, teniendo futura elección de distancia significa acercarse al equilibrio. De manera que el algoritmo es fundamentalmente acerca de cómo decidir si un movimiento pro-elección o la reducción de la elección y la traducción. La no-elección mueve se tejen en el medio.
¿Qué queda por hacer?
Usted todavía tiene que demostrar que esto está bien definido y en realidad un bijection.(construir la inversa, es divertido!)
