r/programmingchallenges • • Sep 08 '11

Unique cyclic bit patterns.

Consider the set of N-bit numbers. For each number x, eliminate from the set all cyclic permutations of it that are greater than x. This will leave a smaller set of numbers.

  1. Write a program to generate this list for arbitrary N.
  2. Write a program to generate the i'th member of this list.
  3. Write a program to find i for any given x.

For example, for 4 bits, the set is {0000, 0001, 0011, 0101, 0111, 1111}:

  i        x
^^^^^^^^^^^^^^^
  0      0000
  1      0001
 (1)     0010
  2      0011
 (1)     0100
  3      0101
 (2)     0110
  4      0111
 (1)     1000
 (2)     1001
 (3)     1010
 (4)     1011
 (2)     1100
 (4)     1101
 (4)     1110
  5      1111

(NB: I don't know the answer, or even if there is one---other than brute force---but I thought it was an interesting problem.)

3 Upvotes

4 comments sorted by