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$?
How do I generate the set of binary strings with elements that are unique under reversal?
1
$\begingroup$
combinatorics
computer-science
-
0@William Chan, Take the set of all unique binary strings of a certain length, and then prune this list of strings s.t. one has the largest possible subset where no two strings are equivalent even if one is allowed to reflect/reverse any binary sequences. – 2011-09-24
2 Answers
2
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}$
1
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}? $