patternMinor
Find all n bit numbers with k ones and unique under circular shift
Viewed 0 times
shiftuniquebitallwithnumbersandundercircularfind
Problem
I am trying to traverse through all uint64_t with k 1s. Then I find that if x and y are circular shifts of each other, they will output the same result. So I'm trying to optimize my code.
The problem is I don't know how to exactly traverse through the set of numbers that has exactly k 1s, and also unique under circular shift.
I have some pretty close attempts that traverse almost without any redundancy. It involves cutting it into sequences of 1 and 0, recording their length, and ensuring the "largest substring of length" is at the lower digit. But it is not perfect.
Is there any elegant way to achieve this?
The problem is I don't know how to exactly traverse through the set of numbers that has exactly k 1s, and also unique under circular shift.
I have some pretty close attempts that traverse almost without any redundancy. It involves cutting it into sequences of 1 and 0, recording their length, and ensuring the "largest substring of length" is at the lower digit. But it is not perfect.
Is there any elegant way to achieve this?
Solution
Binary strings considered up to rotation are known as necklaces. You are interested in enumerating binary necklaces with given density. You can find one solution in Wang and Savage, A Gray Code for Necklaces of Fixed Density.
Context
StackExchange Computer Science Q#148759, answer score: 7
Revisions (0)
No revisions yet.