4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think I have a recursive solution, If you are interested. It uses recursion of depth $\frac{n}{2}$ so it might not be the most efficient way. $\endgroup$ – TheHolyJoker Jan 25 at 10:42
  • $\begingroup$ @TheHolyJoker Still that sounds interesting, feel free to post it if you like (and who knows, someone could get an idea to improve the recursion depth). $\endgroup$ – Sil Jan 25 at 10:46
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (+1) Nice, works like a charm! $\endgroup$ – Sil Jan 25 at 11:17
  • $\begingroup$ @RoddyMacPhee: Please post alternative answers as answers, not as comments to unrelated answers. $\endgroup$ – joriki Jan 25 at 13:16
  • $\begingroup$ Bits to the left of the rightmost zero bit are unaffected by binary addition. Remember reverse(b) and when doing reverse(b+1) work from the right hand end of the input. Stop at the first zero bit in b, and block copy everything to the left from reverse(b). $\endgroup$ – Patricia Shanahan Jan 26 at 8:36
2
$\begingroup$

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...

$\endgroup$
  • 1
    $\begingroup$ Nice, it seems to work (although the termination condition for recursion is a bit tricky for odd lengths). $\endgroup$ – Sil Jan 26 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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