Generar todos los números binarios, un poco solo voltear una vez

Question

¿Es posible generar secuencialmente todas las configuraciones de $n$-poco (digamos, la representación binaria de un un $n$ cifra), un poco solo voltear una vez, de tal manera que ninguna configuración genera dos veces?

En caso afirmativo, ¿existe un algoritmo para el que no es necesario recordar que las configuraciones ya se han generado?

---

Ejemplo para configuraciones de 3 bits

OOO  OOX  OXX  OXO  XXO  XOO  XOX  XXX

Configuraciones posteriores difieren solamente en un solo bit.

Answer 1

Busca códigos gris.

Answer 2

Sí, es posible.

Un flojo inductivo de la prueba: Se ha demostrado que durante tres bits. Si usted puede correr a través de todas las combinaciones de tres bits, puede ejecutar a través de ellos de nuevo. (Que se ejecuta a través de la misma secuencia de bits voltea de nuevo también va a generar todas las tres combinaciones de bits. Los términos en la secuencia particular generada en los tres combinaciones de bits serán de la exclusiva-O de los términos correspondientes en la secuencia que tiene en su pregunta.)

Así, ejecutar a través de todos los tres combinaciones de bits de una vez, voltear el cuarto bit, ejecutar a través de todos los tres combinaciones de bits de nuevo. Ahora usted acaba de ejecutar a través de todos los cuatro combinaciones de bits. Voltear el quinto bit, y ejecutar a través de todos los cuatro combinaciones de bits de nuevo. Repita hasta que usted está enfermo de un tirón bits, y has ganado.