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

Question

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.

Answer 1

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.

Answer 2

Recursive solution
(might not be optimal. Recursion depth is $\frac{n}{2}$)

---

In each step in the recursion, we fix the first and the last character, denoted by $b_1,b_n$. to two cases:

1. $b_1 \neq b_n$
2. $b_1 = b_n$

First case

Solving the first case, is easy (If I'm not wrong). You set the first character to $0$, the last to $1$, (or $b_0=1,b_n=0$ but you don't need both!), and let the substring $b_2...b-{n-1}$ get all other $2^{n-2}$ options.

Second case

The second case, is a bit harder, so we solve it with recursion. We set the first an the last bit once to $0$, and once to $1$, and repeat the previous step.

You get the following recursion depth formula $$D(n) = 2D(n-2)$$

---

Important remark:
The way you want to represent the output is very important. It could easily reduce the depth formula to $D(n) = D(n-2)$

---

Another remark: I don't really see the direct connection, but this question really reminds me of Heap's algorithm, maybe it will give someone good ideas...