[Math] Generate all binary numbers, a single bit flip a time

algorithmscombinatorics

Is it possible to sequentially generate all $n$-bit configurations (say, the binary representation of a an $n$-digit number), a single bit flip a time, in such a way that no configuration is generated twice?

If yes, is there an algorithm for this that doesn't need to remember which configurations have already been generated?


Example for 3-bit configurations

OOO  OOX  OXX  OXO  XXO  XOO  XOX  XXX

Subsequent configurations differ only in a single bit.

Best Answer

You're looking for Gray codes.

Related Question