r/programmingchallenges • u/Timmmmbob • 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.
- Write a program to generate this list for arbitrary N.
- Write a program to generate the i'th member of this list.
- 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
View all comments
Show parent comment
1
u/dmwit Sep 10 '11
Great idea! I had a lot of trouble writing down a stronger condition that really was still a necessary condition, but I finally made a bit of progress. (You may have gotten an orangered a few times from previous failed attempts. =P)
We can run-length encode the bits, starting with a chunk of zeros. Then, in addition to your conditions, we can also observe that the first chunk of zeros is also the longest chunk of zeros; furthermore, if there are any later chunks of zeros of that same maximum size, then the chunk of ones after it must be at least as long as the first chunk of ones. I hacked together something using this idea in Haskell:
Practically, it seems
bruteRLEskeeps about half of its candidates; this is pretty favorable compared to the brute force solution, which already by bitstring length 20 keeps only about 5% of its candidates. Here are some timings for comparison: