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$
  • 1
    $\begingroup$ It holds for all odd $n$ with $f(b) = reverse(b)$ :-) $\endgroup$ – Carl Löndahl Mar 4 '16 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 '16 at 1:16
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$
  • $\begingroup$ Are there some extra $f_n$'s in the description of $f_n$? Otherwise, looks like a solid answer! $\endgroup$ – Fimpellizieri Mar 4 '16 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$ – Carl Löndahl Mar 4 '16 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 '16 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 '16 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 '16 at 2:34

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.