I want an algorithm that generates one representative for every binary string of a fixed length, treating strings as equivalent when one can be obtained from the other by repeatedly moving the rightmost bit to the left. For example, with five bits, 00010 is equivalent to 00001, so only one of them should be listed. Likewise, 00110 belongs to the same group as 00011. The result should contain every rotational equivalence class exactly once, preferably using the numerically smallest or lexicographically smallest rotation as the representative. I may need this for different bit lengths, so leading zeroes should be preserved.
4 Answers
Be careful about the terminology: these strings are not necessarily asymmetric. You are grouping strings into equivalence classes under cyclic rotation and selecting one representative from each class. A string such as 0101 has fewer than n distinct rotations because it repeats, while a string such as 00001 has n distinct rotations. If you instead want only strings with n distinct rotations, keep a string only when the set of its rotations has size n.
You can avoid generating duplicate output by using a direct canonicalization function. In integer form, rotate the n-bit value through all n positions, keep the minimum rotated value, and use that minimum as the key. Pseudocode: for value from 0 to (1<<n)-1, canonical=value; for shift from 1 to n-1, canonical=min(canonical, rotateLeft(value,shift,n)); add canonical to a set. Finally, print each set member as an n-bit binary string so leading zeroes are not lost.
A straightforward way is to enumerate all 2^n bitstrings, generate every cyclic rotation of each one, and choose the smallest rotation as its canonical representative. Store those representatives in a set. If the canonical form is already in the set, skip the string; otherwise add it to the output. For a bitstring s of length n, the canonical form is min(s[i:]+s[:i] for i in range(n)). For five bits this produces representatives such as 00000, 00001, 00011, 00101, 00111, 01011, 01111, and 11111.
For larger lengths, there are specialized generators for binary necklaces that produce one representative directly instead of checking all 2^n values. They are useful when n gets large, but for lengths around 15 or 16, brute force plus canonical rotation is usually simple and fast enough. The number of representatives is given by the necklace-counting formula (1/n) times the sum of phi(d)*2^(n/d) over all divisors d of n.
This is usually called enumerating binary necklaces. The simple method is easy to implement, although it examines every possible bitstring and all of its rotations.