Conjecture about reversal operations on strings (with duplicates)

Question

Note: If you can find a proof of this, please give me just a hint first, so I can try to solve it on my own.

Let $\Sigma$ be a finite alphabet (set of symbols) and $s,t\in\Sigma^\ast$ two strings (sequences of symbols) of equal length $n$ over $\Sigma$. We denote by $s_i\in \Sigma$ the $i$-th symbol of $s$, and by $as\in\Sigma^{n+1}$ the concatenation of the symbol $a\in\Sigma$ with $s\in\Sigma^n$. First, define a reversal operation $\text{r}(i,j)$ on $s$ as the operation:

$$s=s_1...s_n\quad\mapsto\quad s_1...s_{i-1}\ \ s_j s_{j-1}...s_{i+1}s_i\ \ s_{j+1}...s_n$$

that extracts the substring $s_i\dots s_j$ from $s$, reverses it, and puts it back in the same place, where $1 \le i\le j \le n$. Then, define the reversal distance $d_r(s,t)$ between $s$ and $t$ as the minimum number of reversal operations (on either $s$ or $t$) needed to transform $s$ into $t$ ($d_r(s,t):=\infty$ if not possible).

Conjecture: Let $a\in\Sigma$ and $s,t\in\Sigma^n$. Prove (or find a counterexample) that:

$$d_r(as,at)=d_r(s,t)$$

(In other terms, we can disregard the longest common prefix between two given strings when transforming one into the other.) Note that $a$ can occur in $s,t$.

---

Example: $a=1,\ s=23141,\ t=41123$

$$ \begin{array}{cl|cl} as\to^2 at & & s\to^2 t & \\ \hline \underline{1\ 23}141 & \text{r}(1,3)\ & \underline{2314}1 & \text{r}(1,4)\ \\ \underline{3\ 21141} & \text{r}(1,6)\ & 41\underline{321} & \text{r}(3,5)\ \\ 1\ 41123 & & 41123 & \\ \hline \end{array} $$

---

A few remarks:

• That $d_r(as,at)\le d_r(s,t)$ is obvious, the converse less so.
• If $n\gt 0$ and $d_r(as,at)=1$ then $d_r(s,t)=1$.

• If $n\gt 0$ and $a$ does not occur in $s,t$, then it must return at the initial position at some point. Therefore, the same reversal operations that transform $as$ into $at$ can be easily adjusted to transform $s$ into $t$, so that the relative positions between all the other symbols excluding $a$ remain the same. This implies the conjecture in this case.
  
  

• Induction alone doesn't seem to be powerful enough. Also, most results I've found in the literature either provide lower/upper bounds on the minimum $k$, or concern the computational complexity of this kind of problems, collectively known as sorting by reversals.

• I tested it via computer on random instances up to a reasonably high $n$ and it seems to hold.

---

I've edited this question numerous times, mainly to consider some variation of the conjecture. We write $s\to^k t$ if $s$ can be transformed into $t$ by application of exactly $k$ reversals:

• Assume $i\lt j$ (i.e. $\text{r}(i,i)$ are disallowed). Prove that if $as\to^k at$ then $s\to^k t$. Counterexample: $$ \begin{array}{cl|cl} as\to^1 at & & s\to^1 t & \\ \hline \underline{1\ 1}23123... & \text{r}(1,2)\ & 123123... & ? \ \\ 1\ 123123... & & 123123... & \\ \hline \end{array} $$

• Assume $i\lt j$ (i.e. $\text{r}(i,i)$ are disallowed). Prove that if $as\to^k at$ and $s\neq t$ then $s\to^k t$. Counterexample: $$ \begin{array}{cl|cl} as\to^3 at & & s\to^3 t & \\ \hline \underline{1\ 23}4 & \text{r}(1,3)\ & 234 & ? \ \\ 3\ 2\underline{14} & \text{r}(3,4)\ & & ? \ \\ \underline{3\ 241} & \text{r}(1,4)\ & & ? \ \\ 1\ 423 & & 423 & \\ \hline \end{array} $$

• For sake of completeness, the original conjecture above can be practically re-written as: Prove that if $n\gt 0$ and $as\to^k at$ then $s\to^k t$.

---

Edit: Possible counterexample to the original conjecture: $$ \begin{array}{cl|cl} as\to^3 at & & s\to^3 t & \\ \hline \underline{4\ 221}31441 & \text{r}(1,4)\ & 22131441 & ? \ \\ 1\ 2\underline{2431441} & \text{r}(3,9)\ & & ? \ \\ \underline{1\ 2144}1342 & \text{r}(1,5)\ & & ? \ \\ 4\ 41211342 & & 41211342 & \\ \hline \end{array} $$

Answer 1

Here is a check in Python that your proposed counterexample is indeed a counterexample. I took the subflip function from @AleksejsFomins's answer.

import itertools

def subflip(s, i, j):
    return s[:i] + s[i:j][::-1] + s[j:]

s = "22131441"
t = "41211342"

flipped_strings = set([s])
num_flips = 0

while True:
    if t in flipped_strings:
        print("Minimal number of flips:", num_flips)
        break

    new_flipped_strings = set()
    for i, j in itertools.combinations(range(len(s) + 1), 2):
        new_flipped_strings.update(subflip(f, i, j) for f in flipped_strings)

    flipped_strings = new_flipped_strings
    num_flips += 1

The output is (near instantaneously):

Minimal number of flips: 4

And indeed, if you prepend the 4 on both strings this script confirms that three flips suffice to change one string into the other.

Answer 2

I have run a numerical simulation on your proposed counter-example, and the minimal number of flips for the string without prefix is 4, which is more than 3

CODE (Python3)

def subflip(s, i, j):
    return s[:i] + s[i:j][::-1] + s[j:]

s1 = "22131441"
s2 = "41211342"
N = len(s1)

def test(s1, s2, pref, depth):
    for i in range(N-1):
        for j in range(i+2, N+1):
            s1_a = subflip(s1, i, j)
            pref_a = pref+[(i, j)]
            if s1_a == s2:
                print(s1_a, s2)
                print("Win", pref_a)
                return True

            if depth - 1 > 0:
                if test(s1_a, s2, pref_a, depth-1):
                    return True
    return False

test(s1, s2, [], 4)

Answer:

Win [(0, 4), (0, 6), (3, 8), (4, 7)]

Edit: This is a depth-first search, so I ran the code several times for increasing value of depth until I got an answer

Note: I do not believe I deserve the bounty, because you proposed the counter-example yourself, I just checked it