10
$\begingroup$

Is there an algorithm that you can apply twice to an input string of $0$s and $1$s in order to reverse it?

In other words, is there a function $f : \mathrm B \to \mathrm B$ on the set of binary strings $\mathrm B = \{\varepsilon, 0, 1, 00, 01, 10, 11, 000, ...\}$ so that $f(f(b)) = \mathrm{reverse}(b)$ for all $b \in \mathrm B$?

If so, describe such a function/algorithm. If not, prove why it doesn’t exist.

(BONUS: for which other positive integers $n$ is there an algorithm that reverses a string when applied $n$ consecutive times?)

$\endgroup$
2
  • 1
    $\begingroup$ It holds for all odd $n$ with $f(b) = reverse(b)$ :-) $\endgroup$ Mar 4, 2016 at 21:57
  • 1
    $\begingroup$ Impossible, by the way, for all even $n$ if $f(b)$ must have the same length as $b$, as seen from $f(01)$ or $f(10)$ $\endgroup$
    – humn
    Mar 6, 2016 at 1:16

1 Answer 1

12
$\begingroup$

Consider the set of binary strings that are lexicographically earlier than their reverses. For example, 011, 1011, and 11010111 are all members of this set, because 011 is earlier than 110, 1011 is earlier than 1101, and 11010111 is earlier than 11101011. We can order this set by length, followed by lexicographical order. Let the first member (01) be $c_1$, the second member (001) be $c_2$, the third member (011) be $c_3$, and so on. Let $d_i=\text{reverse}(c_i)$.

For an integer $n$, define $f_n$ as follows:

  • For every integer $i$ not a multiple of $n$, $f_n(c_i)=c_{i+1}$ and $f_n(d_i)=d_{i+1}$.
  • For every integer $i$ that is a multiple of $n$, $f_n(c_i)=d_{i+1-n}$ and $f_n(d_i)=c_{i+1-n}$.
  • Otherwise, $f_n(b)=b$.

When $f_n$ is applied $n$ times, the result is the reverse of the input:

  • $f_n^{(n)}(c_i)=d_i$
  • $f_n^{(n)}(d_i)=c_i$
  • $f_n^{(n)}(b)=b$ for all $b$ that are not a $c_i$ or a $d_i$; the only such strings are the ones that are neither earlier than nor later than their reverses, so they are the same as their reverses.
$\endgroup$
10
  • $\begingroup$ Are there some extra $f_n$'s in the description of $f_n$? Otherwise, looks like a solid answer! $\endgroup$ Mar 4, 2016 at 22:11
  • $\begingroup$ Aha, I see, so you are basically mapping the binary sequences to $\mathbb{N}$, moving around in $\mod n$ and then making sure you reverse the intial value only once in the $n$ function calls (using $\mod n$)? $\endgroup$ Mar 4, 2016 at 22:15
  • $\begingroup$ This was exactly my approach! Nice work. I’m interested to see if there are more “natural” such functions $f$. $\endgroup$
    – Lynn
    Mar 4, 2016 at 22:34
  • 1
    $\begingroup$ @hmmn Out of all the strings with length $x$, $2^{\left\lceil{\frac{x}{2}}\right\rceil}$ are palindromes. Out of the rest, half are $c$s and half are $d$s. Knowing this, you can figure out how many $i$s are used for each length. $\endgroup$
    – f''
    Mar 6, 2016 at 2:30
  • 1
    $\begingroup$ @hmmn After that, to determine an index within the strings of length $x$, read the first $\left\lfloor\frac{x}{2}\right\rfloor$ bits as an integer $a$. If $x$ is even, there are $a-1$ $c$s with the same starting bits; if $x$ is odd, there are $2(a-1)$. Beyond that, I don't actually know a good way to find $i$. :/ $\endgroup$
    – f''
    Mar 6, 2016 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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