Complejidad de homogeneizar una cadena

10

Motivación : Mientras desarrollamos herramientas para el control de versiones de datos, terminamos buscando algoritmos para "diferenciar" dos conjuntos de enteros, creando una secuencia de transformaciones que llevan un conjunto de enteros al otro. Pudimos reducir ese problema al siguiente problema muy natural que parece tener conexiones para editar la distancia, la agrupación por intercambio y la mínima partición de cadena común .

Problema : se nos da una cadena, es decir, una secuencia de letras, y nuestro objetivo es homogeneizarla a un costo mínimo. Es decir, queremos una secuencia reorganizada de tal manera que todas las letras que sean iguales estén una al lado de la otra.

La única operación que se permite es recoger una subsecuencia de letras que son parecidas, y mover esa subsecuencia a cualquier lugar, y eso me cuesta 1 unidad.

¡Cualquier ayuda que caracterice la complejidad de este problema sería muy apreciada!

Ejemplo :

  • aabcdab: entrada
  • bcd aa ab: después de mover el primer aa a la posición justo después de "d"
  • b bcdaaa: después de mover el final b a la primera posición

Como la cadena resultante es homogénea, tenemos un costo de 2.

Tenga en cuenta que no estamos limitados de ninguna manera con respecto a la salida: mientras sea homogéneo, no necesitamos asegurar ningún orden específico.

Aditya Parameswaran
fuente

Respuestas:

6

Este problema es NP-completo, por reducción del conjunto de golpes mínimos .

USsS,sUHUsS,hHhs

La reducción es la siguiente:

  • uUussSusu

  • s|s|1suusu

  • ususssSssu

  • |s|+|H|H

Dado que el conjunto de golpe mínimo es NP-Hard, también se homogeneiza de manera óptima una cuerda. Como los movimientos forman un testigo, es NP-Completo.

isaacg
fuente
Esta es una reducción elegante, ¡gracias!
Aditya Parameswaran
2

Mire el número de cambios de una letra a la otra en su cadena, que podría ver como una medida de la falta de homogeneidad de la cadena. Con cada movimiento (útil) de una subsecuencia, reduce este número en uno si la subsecuencia que mueve está precedida y seguida por dos letras distintas. De lo contrario, reduce la falta de homogeneidad en dos.

Entonces, para una cadena con k cambios, necesita como máximo k - l + 1 se mueve donde l es el número de letras diferentes en la cadena, porque al final permanecerán los cambios l - 1 . Como una cadena de longitud n puede tener como máximo n-1 cambios de letras, puede necesitar como máximo n-l movimientos. El menor número posible es la mitad de esto.

Así, la mejor estrategia parece buscar subsecuencias de la forma abbba y alejar el bbb de allí. Cuando no quede ninguno, mueva lo que sea. Todavía podría intentar hacer esas operaciones que crean nuevas situaciones de abbba, pero creo que la ganancia será muy pequeña. Dado que la peor estrategia posible (sin movimientos tontos que aumentan la falta de homogeneidad) utiliza como máximo el doble de movimientos que el óptimo, lo poco que puede ganar parece no tener una relación razonable con el esfuerzo como la respuesta de isaacg con la caracterización como NP-hard sugiere. A menos, por supuesto, que realmente solo cuente el número de operaciones de movimiento y no le importe el tiempo para decidir qué movimientos hacer.

Por lo tanto, el peor de los casos es una cadena en la que cada letra es diferente de su predecesora (y no obtienes ningún bono de abbba). Aquí necesita una serie de operaciones lineales en la longitud de la cadena y casi igual a esta longitud.

En su ejemplo, tiene 5 -> 4 -> 3 cambios, y 3 es igual al número de letras (4) menos 1.

Nota al margen: para un alfabeto de tamaño solo dos, cada movimiento que no mueve un prefijo o sufijo de la cuerda reduce la falta de homogeneidad en dos y, por lo tanto, cada secuencia de movimientos razonables es óptima.

Peter Leupold
fuente
Afirma que un movimiento puede reducir el número de cambios como máximo en 2, pero en realidad puede reducir el número de cambios hasta en 3. Por ejemplo, convertir "aabcabc" en "aaabbcc" moviendo la primera subcadena "bc" a la mitad de la segunda subcadena "bc" da como resultado una disminución del número de cambios en la cadena de 5 a 2.
Mikhail Rudoy
Hola, @MikhailRudoy. Las preguntas indican que la operación es "recoger una subsecuencia de letras que son similares", por lo que no se permite bc hasta donde yo entiendo.
Peter Leupold
Extrañé completamente ese detalle. Tienes razón en ese caso.
Mikhail Rudoy
Peter tiene razón: esos movimientos no están permitidos.
Aditya Parameswaran
Re: el resto de la respuesta; de hecho, estas observaciones re: límites inferiores, la optimización del caso del tamaño del alfabeto 2 y la heurística de qué hacer en cualquier momento son valiosas. Dado que cualquier movimiento en el peor de los casos solo beneficia esa secuencia de letras y, en el mejor de los casos, combina a lo sumo dos secuencias de letras como en su abbba, una aproximación de 2 parece natural.
Aditya Parameswaran