You have an N-bit (boolean) array, where N is odd, for which you must produce all possible permutations of bits. Write a function that can produce the sequence of all possible n-bit permutations, with the following restrictions:This seemingly simple problem requires some careful thought to solve correctly. Look for the solution in the coming days on my blog.
- The first value in the permutation sequence must consist of all zeros.
- The last value in the permutation sequence must consist of all ones.
- Each n-bit permutation must vary by only one bit from the prior permutation.
- No duplicate permutations must be produced.
- No permutations should be omitted from the sequence.
- Generating each permutation should require constant time.
Thursday, June 18, 2009
Programming Puzzle - N-Bit Array Permutation
Here's a programming puzzle that came out of an interesting experience working on a recent project of mine.