Is there an algorithm for generating bit patterns unique under complementation and rotation? Does anyone know of an algorithm for generation of unique bit patterns of $N$ bits, where $N > 1$, fitting constraints of being unique under complement and rotation of the bits?
For example, say, if $N$ is $5$ bits : so, patterns of $00000$ through $11111$
which must be different from their bits complement: $01011$ means not also $10100$.
and also must be different from any rotation of those bits of same length: $01011$ means not also $10110$ or $01101$ or $11010$ or $10101$.
I want to go to larger $N$ with this (say up to $128$ bits or more depending on the time required) so efficiency is needed. Is there an algorithm to generate these directly without needing extra processing and memory to filter duplicates?
 A: You're asking for something that outputs a member of each equivalence class, where two bit patterns are equivalent if they are the same under rotation and/or complementation. One way to do this is with a choice function: a function that takes an equivalence class and outputs a particular member of the equivalence class. If we have such a function $f$, we can do the following:

Iterating over all bit patterns $s$, compute the equivalence class $S$ which contains $s$, and output $s$ if and only if $s=f(S)$.

This way, the elements output will be exactly those $s$ which are $f(S)$ for their equivalence class $S$. This algorithm takes time $2^N$ times the amount of time it takes to compute $f(S)$ given $s$, which (if $f$ can be computed efficiently) is not that much worse than the number of outputs, which is at least about $\frac{2^N}{2N}$ (since every equivalence class has at most $2N$ elements). The benefit of this is that it requires very little memory: you don't need to store and check anything like "the list of all bit patterns you've already output."
One easy choice for $f$ is for $f(S)$ to be the element which is lexicographically earliest. For example, for $N=3$, the equivalence class of $010$ consists of $\{010,001,100,110,011,101\}$. If you write all of these numbers out, sorted by first bit, with ties broken by second bit, then third bit, etc., the first is $001$. To compute this isn't that hard: you just need to compute all of the elements in $S$ and find the earliest one, which only involves about $2N$ comparisons.
So, this algorithm isn't quite as efficient as one could hope (runtime about $N2^N$ instead of about $2^N/N$), but I'd suspect the differences in practicality aren't that large between this and a faster algorithm. Because $2^N$ grows so much more quickly than $N$, any algorithm which outputs every such bit pattern is going to be very impractical for large enough $N$ ($40$ would probably be pushing it).

If you're looking for a way to only output a few of these (i.e. not a member from every equivalence class, just some of them) but be sure you don't have any duplicates, you can do the same process, but just stop at some point. If you want to be getting the patterns somewhat randomly, you can use a pseudorandom number generator to go through the bit patterns $s$ (and still only output if $s=f(S)$); one simple-ish way is as follows, representing bit strings of length $N$ as numbers between $0$ and $2^N-1$.

*

*Fix a prime $p>2^N$.

*Fix random $a,b\in\{1,\dots,p-1\}$, and define the function $f:x\mapsto (ax+b)\bmod p$, where $\bmod$ denotes taking the remainder.

*Compute $f(0)$, then $f(1)$, then $f(2)$, et cetera. For the values less than $2^N$, view these as bit strings $s$, and output $s$ if and only if $s=f(S)$. For the others, disregard.

Since $ax+b\not\equiv ay+b\pmod p$ for any $x\not\equiv y\pmod p$, no bit pattern $s$ will show up twice with this method (until you get all the way up to $f(p)$, at which point you've exhausted all of the patterns).
