Conjetura sobre operaciones de reversión en cadenas (con duplicados)

Question

Nota: Si puedes encontrar una prueba de esto, por favor dame solo una pista primero para intentar resolverlo por mi cuenta.

Sea $\Sigma$ un alfabeto finito (conjunto de símbolos) y $s,t\in\Sigma^\ast$ dos cadenas (secuencias de símbolos) de igual longitud $n$ sobre $\Sigma$. Denotamos por $s_i\in \Sigma$ al símbolo $i$-ésimo de $s$, y por $as\in\Sigma^{n+1}$ a la concatenación del símbolo $a\in\Sigma$ con $s\in\Sigma^n$. Primero, define una operación de reversión $\text{r}(i,j)$ en $s$ como la operación:

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

que extrae la subcadena $s_i\dots s_j$ de $s$, la invierte, y la vuelve a colocar en el mismo lugar, donde $1 \le i\le j \le n$. Luego, define la distancia de reversión $d_r(s,t)$ entre $s$ y $t$ como el número mínimo de operaciones de reversión (en $s$ o $t$) necesarias para transformar $s$ en $t$ ($d_r(s,t):=\infty$ si no es posible).

Conjetura: Sea $a\in\Sigma$ y $s,t\in\Sigma^n$. Demuestra (o encuentra un contraejemplo) que:

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

(En otras palabras, podemos ignorar el prefijo común más largo entre dos cadenas dadas al transformar una en la otra.) Nota que $a$ puede ocurrir en $s,t$.

---

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

---

Unas observaciones:

• Que $d_r(as,at)\le d_r(s,t)$ es obvio, lo contrario menos.

• Si

  $n\gt 0$ y $d_r(as,at)=1$ entonces $d_r(s,t)=1$.

• Si $n\gt 0$ y $a$ no ocurre en $s,t$, entonces debe regresar a la posición inicial en algún momento. Por lo tanto, las mismas operaciones de reversión que transforman $as$ en $at$ se pueden ajustar fácilmente para transformar $s$ en $t$, de modo que las posiciones relativas entre todos los demás símbolos excluyendo $a$ permanezcan iguales. Esto implica la conjetura en este caso.

• La inducción por sí sola no parece ser lo suficientemente potente. Además, la mayoría de los resultados que he encontrado en la literatura proporcionan límites inferiores/superiores en el número mínimo $k$, o se refieren a la complejidad computacional de este tipo de problemas, conocidos colectivamente como ordenar por reversión.

• Lo probé mediante computadora en instancias aleatorias hasta un $n$ razonablemente alto y parece ser cierto.

---

He editado esta pregunta numerosas veces, principalmente para considerar alguna variación de la conjetura. Escribimos $s\to^k t$ si $s$ puede transformarse en $t$ mediante la aplicación de exactamente $k$ reversos:

• Supongamos que $i\lt j$ (es decir, se desautorizan los $\text{r}(i,i)$). Demuestra que si $as\to^k at$ entonces $s\to^k t$. Contraejemplo: $$ \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} $$

• Supongamos que $i\lt j$ (es decir, se desautorizan los $\text{r}(i,i)$). Demuestra que si $as\to^k at$ y $s\neq t$ entonces $s\to^k t$. Contraejemplo: $$ \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} $$

• Por completitud, la conjetura original arriba puede ser prácticamente reescrita como: Demuestra que si $n\gt 0$ y $as\to^k at$ entonces $s\to^k t$.

---

Edición: Posible contraejemplo a la conjetura original: $$ \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

Aquí hay una verificación en Python de que tu contraejemplo propuesto es realmente un contraejemplo. Tomé la función subflip de la respuesta de @AleksejsFomins.

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("Número mínimo de 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

La salida es (casi instantánea):

Número mínimo de flips: 4

Y de hecho, si antepone el 4 en ambas cadenas, este script confirma que tres flips son suficientes para cambiar una cadena en la otra.

Answer 2

He realizado una simulación numérica en tu contraejemplo propuesto, y el número mínimo de volteos para la cadena sin prefijo es 4, lo cual es más de 3

CÓDIGO (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("Ganar", 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)

Respuesta:

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

Edición: Esta es una búsqueda en profundidad, así que ejecuté el código varias veces para un valor creciente de profundidad hasta obtener una respuesta

Nota: No creo merecer la recompensa, porque tú mismo propusiste el contraejemplo, sólo lo verifiqué