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.
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:
  • 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.
This seemingly simple problem requires some careful thought to solve correctly. Look for the solution in the coming days on my blog.

1 comment:

Anonymous said...

This sounds closely related to the question I just posted at stackoverflow: Stepping through all permutations one swap at a time.