6
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Fantastic answer! I was told that it is called necklace, but putting necklace as a keyword on google led me completely astray and then I got totally clueless about what to search for. $\endgroup$
    – Billy Yan
    Jan 29, 2022 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.