Is there an efficient algorithm for iterating over binary strings where each of the reciprocal is enumerated exactly once

algorithmsbinarycombinatorics

Problem. Say we have binary strings of length $n$, i.e. $b_1b_2\dots b_n$. There are $2^n$ of such strings, but in this problem if two strings are reciprocal of each other (have same digits in reverse order), we need to iterate just over one of these. For example we do not want to iterate over $1011$ if we have already gone over $1101$. Now the question is how most efficiently can this be done?

Attempts.
We can iterate over all binary strings of given length, and for each string we encounter, we can evaluate the string only if it is "$\leq$" than its reciprocal, where "$\leq$" is any ordering on the strings. For example we can interpret the the string as a binary representation of a number and compare those. In the case above, $(1011)_2=11$ and $(1101)_2=13$ and so if we get to $1011$, we notice $11\leq 13$ and evaluate that one, whereas at $1101$ we have $13>11$ and ignore that one. Problem is that this approach still requires to iterate over all of $2^n$ strings, I was wondering if we can somehow shortcut this and iterate, ideally, directly over the "desired" strings. Perhaps some clever ordering on the strings would do the job.

Motivation. This came up when I wanted to iterate over polynomials with $0,1$ coefficients and check if they satisfy certain property, and it turns out that property will be the same for each of the reciprocal, so I just need to check one of those.

Best Answer

For even $n$: For all strings $a$ of length $\frac n2$, for all strings $b$ of length $\frac n2$ with $b\le a$, generate $ab^{-1}$.

In pseudocode:

for a = 0 .. 1 << n/2 - 1
    for b = 0 .. a
        output (a << n/2) | reverse (b)

For odd $n$, you can do basically the same thing, but with special treatment for the middle digit.

Reversing bit strings is rather expensive, so you’ll probably want to use a look-up table for that.

Related Question