15
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ I don't know what the etiquette is but thank you, @Alexander Gruber, for having placed a bounty on this. $\endgroup$ – giofrida Apr 28 at 17:46
  • $\begingroup$ Interesting question! What about claiming $s \to^{\ell} t$ for some $\ell \leq k$ ? $\endgroup$ – darij grinberg Apr 28 at 23:50
  • $\begingroup$ 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. $\endgroup$ – giofrida Apr 29 at 0:01
  • $\begingroup$ But if you allow degenerate reversals, then why are your counterexamples counterexamples? $\endgroup$ – darij grinberg Apr 29 at 0:02
  • 1
    $\begingroup$ 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. $\endgroup$ – darij grinberg Apr 29 at 0:07
5
+200
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – giofrida Apr 29 at 13:02
  • $\begingroup$ @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. $\endgroup$ – Mees de Vries Apr 29 at 13:04
  • $\begingroup$ @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 :) $\endgroup$ – Aleksejs Fomins Apr 29 at 13:06
  • $\begingroup$ @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$. $\endgroup$ – Mees de Vries Apr 29 at 13:15
  • $\begingroup$ Hmm, you are right! My intuition told me that it was much more :D $\endgroup$ – Aleksejs Fomins Apr 29 at 13:58
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mees de Vries Apr 29 at 12:00
  • $\begingroup$ 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. $\endgroup$ – giofrida Apr 29 at 12:03
  • $\begingroup$ 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. $\endgroup$ – giofrida Apr 29 at 12:38
  • 1
    $\begingroup$ Ah, sorry, I should have mentioned that I had run the code incrementally for different depth until I got a result. I know that it is depth-first search. But if you run it for 3, it does not find the solution, so I think the result is solid. If people insist that I rewrite it as a breath-first-search, I can do that $\endgroup$ – Aleksejs Fomins Apr 29 at 12:53
  • 1
    $\begingroup$ @giofrida No worries, I see everybody here is a gentleman, so he can have it :) $\endgroup$ – Aleksejs Fomins Apr 29 at 13:59

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.