Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
There is a very good chapter in Knuth: 'The art of computer programming' about this. It's 4.something if I remember well. –  Ragnar Dec 20 '13 at 19:43

2 Answers 2

up vote 21 down vote accepted

You're looking for Gray codes.

share|improve this answer
    
Exactly what I would have said but you beat me to it. –  Carl Witthoft Dec 20 '13 at 22:39

Yes, it's possible.

A loose inductive proof: You've demonstrated it for three bits. If you can run through all combinations of three bits, you can run through them again. (Running through the same sequence of bit flips again will also generate all three-bit combinations. The terms in the particular sequence of generated three-bit combinations will be the exclusive-OR of the corresponding terms in the sequence you have in your question.)

So, run through all three-bit combinations once, flip the fourth bit, run through all three-bit combinations again. Now you've just run through all four-bit combinations. Flip the fifth bit, and run through all four-bit combinations again. Repeat until you're sick of flipping bits, and you've won.

share|improve this answer
    
An important step here that you did not spell out is that if it's possible to do it for 3 bits starting from one configuration, it's also possible to do it starting from any other configuration. This is because the actual configuration doesn't matter. It's only the sequence of flips that matters. The same sequence of flips will do it for any starting configuration. (Sorry about the imprecise language.) –  Szabolcs Dec 20 '13 at 19:53
    
Good point. I added a couple of sentences to flesh that out a bit. –  John Dec 20 '13 at 20:18
1  
You want your second run through to be in reverse order. Take OP's series for 3 bits, prefix it with 0, then append the 3 bit series in reverse order prefixed with 1. At the joint we have OXOX OXXX XXXX XXOX and end with XOOX XOOO. –  Ross Millikan Dec 20 '13 at 20:56
    
@Ross: You can either do the second run in reverse order, or do it in the original order but XOR everything with an appropriate constant to make the first element of the second run match the last element of the first run. If start from the base case 0, 1, then these two ways of doubling the length actually end up with the same sequence in the end! –  Henning Makholm Dec 21 '13 at 14:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.