Encontrar anagramas interesantes

Digamos que y b 1 b 2 ... b n son dos cadenas de la misma longitud. Una anagramación de dos cadenas es un mapeo biyectivo p : [ 1 ... n ] → [ 1 ... n ] tal que a i = b p ( i ) para cada i .$a_1a_2\ldots a_n$$b_1b_2\ldots b_n$$p:[1\ldots n]\to[1\ldots n]$$a_i = b_{p(i)}$$i$

Puede haber más de un anagrama para el mismo par de cadenas. Por ejemplo, si `abcab` yb = tenemos p 1 [ 1 , 2 , 3 , 4 , 5 ] → [ 4 , 5 , 1 , 2 , 3 ] y p 2 [ 1 , 2 , 3 , 4 , 5 ] → [ 2 , 5 , $a=$$b=$cabab$p_1[1,2,3,4,5]\to[4,5,1,2,3]$ , entre otros.$p_2[1,2,3,4,5] \to [2,5,1,4,3]$

Diremos que el peso de una anagramación p es el número de cortes que uno debe hacer en la primera secuencia para obtener trozos que se pueden reorganizar para obtener la segunda secuencia. Formalmente, este es el número de valores de i ∈ [ 1 … n - 1 ] para los cuales p ( i ) + 1 ≠ p ( i + 1 ) . Es decir, es el número de puntos en los que p no no aumentar en un ejemplo exactamente 1.Para, w ( $w(p)$$p$$i\in[1\ldots n-1]$$p(i)+1\ne p(i+1)$$p$ y w ( p 2 ) = 4 , porque p 1 cortesuna vez, en los trozosy, y p 2 cortescuatro veces, en cinco trozos.$w(p_1) = 1$$w(p_2) = 4$$p_1$1234512345$p_2$12345

Supongamos que existe un anagrama para dos cadenas y b . Entonces, al menos un anagrama debe tener menos peso. Digamos que este es el más ligero . (Puede haber múltiples anagramaciones más ligeras; no me importa porque solo estoy interesado en las pesas).$a$$b$

Pregunta

Quiero un algoritmo que, dadas dos cadenas para las cuales existe un anagramación, produzca eficientemente el peso exacto de la anagramación más ligera de las dos cadenas. Está bien si el algoritmo también produce un anagrama más ligero, pero no es necesario.

Es bastante simple generar todos los anagramas y pesarlos, pero puede haber muchos, por lo que preferiría un método que encuentre directamente los anagramas ligeros.

Motivación

La razón por la cual este problema es de interés es la siguiente. Es muy fácil hacer que la computadora busque en el diccionario y encuentre anagramas, pares de palabras que contienen exactamente las mismas letras. Pero muchos de los anagramas producidos no son interesantes. Por ejemplo, los ejemplos más largos que se encuentran en el Segundo Diccionario Internacional Webster son:

colecistoduodenostomía
duodenocolecistostomía

El problema debe quedar claro: estos son poco interesantes porque admiten un anagramico muy ligero que el simple intercambio del cholecysto, duedenoy stomysecciones, para un peso de 2. Por otro lado, este ejemplo mucho más corto es mucho más sorprendente e interesante:

sección costera

Aquí el anagrama más ligero tiene peso 8.

Tengo un programa que utiliza este método para localizar anagramas interesantes, a saber, aquellos para los cuales todos los anagramas son de alto peso. Pero lo hace generando y sopesando todos los anagramas posibles, lo cual es lento.

Este problema se conoce como el "problema de la partición de cadena común mínima". cada letra aparece como máximo dos veces en cada una de las cadenas de entrada, como lo demuestran Goldstein, Kilman y Zheng [GKZ05]. Esto significa que no existe un algoritmo de tiempo polinómico a menos que P = NP. (Por supuesto, si cada letra aparece como máximo una vez, entonces el problema es trivial porque solo hay un anagrama.)

En el lado positivo, los mismos autores [GKZ05] dan un algoritmo de aproximación 1.1037 de tiempo polinómico bajo la misma restricción. (Un " algoritmo de aproximación 1.1037 " significa un algoritmo que puede no dar la respuesta correcta A pero se garantiza que dará un valor B tal que A ≤ B ≤ 1.1037 A. ) También dan un algoritmo de aproximación de tiempo lineal 4 bajo el restricción más débil de que cada letra aparece como máximo tres veces en cada una de las cadenas de entrada.

[GKZ05] Avraham Goldstein, Petr Kolman y Jie Zheng. Problema mínimo de partición de cadena común: dureza y aproximaciones. Electronic Journal of Combinatorics , 12, artículo R50, 2005. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50

Este es un seguimiento de la respuesta anterior de Tsuyoshi Ito , que resume la parte más relevante del documento GKZ05 que citó.

$G$$(i, j)$$a_i = b_j$$a_{i+1} = b_{j+1}$$(i, j)$$(k, \ell)$$i≤k$$i\mapsto j$$i+1\mapsto j+1$$k\mapsto\ell$$k+1\mapsto\ell+1$

1. $i=k$$j\ne\ell$
2. $i+1=k$$j+1\ne\ell$
3. $i+1<k$$\{j, j+1\}$$\{\ell, \ell+1\}$

$G$$s$$n-s-1$$n$$a$$b$$G$

yttrioustouristyouriououriri$s=2$y|t|t|ri|ou|st|ou|ri|s|t|y

Por otro lado, considere deratery treader. Esta vez el gráfico tiene tres vértices:

1. DErater + treaDEr
2. dERater + treadER
3. deratER + treadER

$s=2$der|a|t|e|rt|r|e|a|der

No cubre el algoritmo exacto que tenía en mente (lo que hace la respuesta de Tsuyoshi Ito ), pero trata de llegar al problema subyacente de encontrar anagramas "interesantes" ...

Mi primer pensamiento fue usar alguna variación en la distancia de edición, donde los cambios atómicos se ponderan de acuerdo con su "interés" en lugar de las ponderaciones habituales de "dificultad" o "confusabilidad". Por supuesto, parece poco probable que pueda codificar eficientemente las transformaciones realmente interesantes de esta manera, ya que es probable que no sean locales y, por lo tanto, se encuentren con los problemas NP-completos de MIS, etc.

Por lo tanto, lo segundo sería construir una alineación letra a letra entre las palabras (alineaciones a la traducción automática), y luego calificar las alineaciones por "interés" (por ejemplo, contar las alineaciones que llevan letras adyacentes a letras adyacentes, o cuántas alineaciones cruza cada alineación, etc., y luego combinarlas todas a través de un modelo loglineal o similar).

La tercera idea es abandonar por completo la estructura del anagrama en sí mismo y, en cambio, observar la semántica de las palabras. A menudo, lo que hace que un anagrama sea "interesante" es la incongruencia entre los significados de las palabras involucradas. Así que intente algo como calcular su distancia en WordNet, o similar.

El problema puede expresarse en términos de grupos de permutación .

Ahora un grupo de permutación contiene todos los "movimientos de anagrama", tanto primitivos (intercambiando dos letras) como compuestos de secuencias de movimientos primitivos. Parece que solo le interesa un subconjunto de las posibles permutaciones. Intentaré definir esto.

Primero, recuerde la notación para permutaciones, a saber, la llamada notación de ciclo :

• $()$
• $(1)$
• $(12)$
• $(123)$
• y así uno

Estos simples 'ciclos' están compuestos para describir permutaciones más complejas.

$n$

• $(12)$
• $(a\ b)(a+1\ b+1)$$a>0$$b<a+1$$b+1\le n$
• ...
• $(a\ b)(a+1\ b+1)\cdots(a+i-1\ b+i-1)$$a>0$$a+i-1\le b$$b+i-1\le n$

Estos movimientos forman la base de su algoritmo. Lo que le interesa es encontrar la secuencia más pequeña de estos movimientos para pasar de una palabra a la siguiente.

No conozco ningún algoritmo para calcular esto, aparte de la búsqueda de fuerza bruta, pero al menos ahora hay una descripción más clara (espero) de cuáles son los movimientos primitivos. (Y tal vez algún teórico de grupo entre nosotros pueda apuntar a un algoritmo apropiado).

Para la colecistoduodenostomía / duodenocolecistostoma, noto que si asigna un número a cada personaje que describa cuánto se movió como un delta, tendría algo como 7 7, luego 8 -7, luego 6 0. Eso no está bien porque algunos caracteres pueden haberse repetido (el segundo c solo se movió hacia adelante 2, no hacia atrás 7), etc. pero aún así es muy "codificable por longitud de ejecución" porque ve los mismos deltas seguidos.

Compare con la línea de costa / seccional, donde ve algo como (+2) (+ 5) (+ 5) (- 3) (- 1) (+ 3) ... mucho menos "longitud de ejecución codificable".

¿Quizás la aleatoriedad de los deltas podría darle una "puntuación" en cuanto a lo interesante que es el anagrama?