How do I generate the set of binary strings with elements that are unique under reversal?

Question

What is the most efficient way to generate the set $S$ of unique binary strings of a certain length, $L$, s.t. all strings are unique under the reversal operation? For example, if $L = 2$, the elements of $S$ would be {00, 01, 11}. Also, what is $||S||$ as a function of $L$?

Answer 1

Generate all strings of length $L$ and discard those that are lexicographically greater than their reverse.

This number of strings this produces is $2^L$ minus half of the number of strings that are not palindromes. There are $2^{\lceil L/2 \rceil}$ palindromes, so $$|S| = 2^L - \frac{2^L - 2^{\lceil L/2\rceil}}{2} = 2^{L-1} + 2^{\lceil L/2\rceil-1}$$

Answer 2

For every string $x$,

• If $x$ is a palindrome ($x = x^R$), pick it.
• Otherwise, pick either $x$ or $x^{R}$, but not both.

The maximum size of $S$ is $$ \frac{2^L - P}{2} + P = \frac{2^L+P}{2}, $$ where $P$ is the number of palindromes of length $L$. Can you see why $P$ is equal to $$ 2^{\lceil \frac{L}{2} \rceil}? $$