Conjecture about reversal operations on strings (with duplicates)

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}$$

• I don't know what the etiquette is but thank you, @Alexander Gruber, for having placed a bounty on this. – giofrida Apr 28 at 17:46
• Interesting question! What about claiming $s \to^{\ell} t$ for some $\ell \leq k$ ? – darij grinberg Apr 28 at 23:50
• I think it would be equivalent, since you could always complete the sequence of $\mathscr{l}$ reversal operations with $k-\mathscr{l}$ degenerate reversals. Instead, I was thinking of imposing $s\neq t$ and $n\ge |\Sigma|$, or something similar, but I don't really like it because it's getting complicated. – giofrida Apr 29 at 0:01
• But if you allow degenerate reversals, then why are your counterexamples counterexamples? – darij grinberg Apr 29 at 0:02
• PS. I assume you have read Anne Bergeron, Julia Mixtacki, and Jens Stoye, The inversion distance problem? I think they never go beyond the case of permutations, but there may be useful ideas in there. – darij grinberg Apr 29 at 0:07

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.

• Ok, this seems correct. The argument is as follows: suppose $s\to^k t$. If $k=0$ then $s=t$ and this would be discovered upon entering the main cycle. Else there must be some $t'$ such that $s\to^{k-1} t'\to^1 t$. By inductive hypothesis $\text{flipped_strings}$ contained the endpoints of all the possible paths of length $k-1$ from $s$ to another string wrt. the relation $\to^1$, including $t'$, at the previous iteration. Therefore, assuming the update is correct, it necessarily contains $t$ at the current iteration. This covers the minimal case, too. – giofrida Apr 29 at 13:02
• @giofrida, indeed, that's what it's supposed to do. i, j take on all values $0 \leq i < j \leq \mathrm{len}(s)$, and .update puts all the newly flipped strings into new_flipped_strings. – Mees de Vries Apr 29 at 13:04
• @MeesdeVries neat solution, to store all flipped strings, I would not have thought of that. A bit scary for exponential problems, as memory could blow up, but in this case it works fine :) – Aleksejs Fomins Apr 29 at 13:06
• @AleksejsFomins, in general it is not great, but we are talking about strings of length 8, so a strict upper bound is $8! \approx 40000$. – Mees de Vries Apr 29 at 13:15
• Hmm, you are right! My intuition told me that it was much more :D – Aleksejs Fomins Apr 29 at 13:58

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)


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

• I might be mistaken here but at first glance it doesn't seem like this code searches for the least number of reversals required; it finds something like the reversal that is "lexicographically" earliest. Specifically, if there is a way to flip $s, t$ in three flips, but the first flip in this sequence of three is $(1, 5)$, I do not think your code finds it. – Mees de Vries Apr 29 at 12:00
• Well, I suppose the bounty has to go to someone, after all. I'm not familiar with Python so I'll need some time to check your code, then I'm going to accept your answer (by the way, I'd obtained your same result, i.e. $k=4$). Edit: I didn't see @MeesdeVries' comment, and yes, it looks like it does a sort of depth-first search. – giofrida Apr 29 at 12:03
• So, yes, in general it is incorrect. E.g. with $s_1 =112$, $s_2 =121$ and $\text{depth}=2$ it returns [(0, 2), (1, 3)]. Also, just a note: I think you could've written if depth - 1 > 0: return test(...) at line 19. – giofrida Apr 29 at 12:38