string - por - operaciones con cadenas en c

Encontrar el número mínimo de swaps para convertir una cadena a otra, donde las cadenas pueden tener caracteres repetidos

Question

Estaba mirando a través de una pregunta de programación, cuando la siguiente pregunta de repente parecía relacionada.

¿Cómo convertir una cadena en otra cadena usando tan pocos swaps como sigue? Se garantiza que las cadenas son interconvertibles (tienen el mismo conjunto de caracteres, esto se da), pero los caracteres pueden repetirse . Vi resultados web sobre la misma pregunta, sin que los caracteres se repitieran. Cualquiera de los dos caracteres en la cadena puede ser intercambiado.

Por ejemplo: "aabbccdd" se puede convertir a "ddbbccaa" en dos swaps, y "abcc" se puede convertir a "accb" en un swap.

¡Gracias!

Answer 1

Esta es una versión expandida y corregida de la respuesta de Subhasis .

Formalmente, el problema es, dado un alfabeto de n letras V y dos palabras de letras m , xey , para las cuales existe una permutación p tal que p ( x ) = y , determina el menor número de intercambios (permutaciones que corrigen todos menos dos elementos) cuya composición q satisface q ( x ) = y . Asumiendo que las palabras de la letra n son mapas del conjunto {1, ..., m } a V y que p y q son permutaciones en {1, ..., m }, la acción p ( x ) se define como la composición p seguido de x .

El menor número de swaps cuya composición es p puede expresarse en términos de la descomposición del ciclo de p . Cuando j ₁ , ..., j _k se distinguen por pares en {1, ..., m }, el ciclo ( j ₁ ... j _k ) es una permutación que asigna j _i a j _{i + 1} para i en {1, ..., k - 1}, mapea jk a j ₁ , y mapea todos los demás elementos a sí mismo. La permutación p es la composición de cada ciclo distinto ( j p ( j ) p ( p ( j )) ... j '' ), donde j es arbitrario y p ( j '') = j . El orden de la composición no importa, ya que cada elemento aparece exactamente en uno de los ciclos compuestos. Un ciclo de elementos k ( j ₁ ... j _k ) se puede escribir como el producto ( j ₁ j _k ) ( j ₁ j _{k - 1} ) ... ( j ₁ j ₂ ) de k - 1 ciclos. En general, cada permutación puede escribirse como una composición de m swaps menos el número de ciclos que comprenden su descomposición del ciclo. Una prueba de inducción directa muestra que esto es óptimo.

Ahora llegamos al corazón de la respuesta de Subhasis. Las instancias del problema del autor de la pregunta se corresponden entre sí con eulerianas (para cada vértice, el grado equivale a un grado superior) los dígrafos G con los vértices V y m arcos marcados con 1, ..., m . Para j en {1, ..., n }, el arco etiquetado j va de y ( j ) a x ( j ). El problema en términos de G es determinar cuántas partes puede tener una partición de los arcos de G en ciclos dirigidos. (Dado que G es Euleriano, tal partición siempre existe). Esto se debe a que las permutaciones q son tales que q ( x ) = y están en una correspondencia de uno a uno con las particiones, de la siguiente manera. Para cada ciclo ( j ₁ ... j _k ) de q , hay una parte cuyo ciclo dirigido se compone de los arcos etiquetados j ₁ , ..., j _k .

El problema con la reducción de la dureza NP de Subhasis es que el empaquetamiento del ciclo de separación del arco en los dígrafos Eulerianos es un caso especial del empaquetamiento del ciclo de separación del arco en los dígrafos generales, por lo que un resultado de la dureza NP para este último no tiene implicaciones directas para el estado de complejidad de el primero Sin embargo, en un trabajo muy reciente (ver la cita a continuación), se ha demostrado que, de hecho, incluso el caso especial de Euler es difícil para NP. Así, por la correspondencia anterior, el problema del que pregunta también lo es.

Como sugerencias de Subhasis, este problema se puede resolver en tiempo polinomial cuando n , el tamaño del alfabeto, es fijo (se puede tratar con parámetros fijos). Ya que hay ciclos O ( n !) Distinguibles cuando los arcos no están marcados, podemos usar la programación dinámica en un espacio de estado de tamaño O ( m ⁿ ), el número de subgrafos que se pueden distinguir. En la práctica, eso podría ser suficiente para (digamos) un alfabeto binario, pero si intentara tratar de resolver este problema exactamente en instancias con alfabetos grandes, entonces probablemente trataría de derivar y enlazar, obteniendo límites mediante la programación lineal. Con generación de columnas para empaquetar los ciclos de forma fraccionada.

@article{DBLP:journals/corr/GutinJSW14,
  author    = {Gregory Gutin and
               Mark Jones and
               Bin Sheng and
               Magnus Wahlstr{/"o}m},
  title     = {Parameterized Directed /$k/$-Chinese Postman Problem and /$k/$
               Arc-Disjoint Cycles Problem on Euler Digraphs},
  journal   = {CoRR},
  volume    = {abs/1402.2137},
  year      = {2014},
  ee        = {http://arxiv.org/abs/1402.2137},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Answer 2

La estructura de datos Hash Map (que permite duplicados) es adecuada para resolver el problema.

Deje que la cadena sea s1 y s2. El algoritmo recorre tanto la cadena como cada vez que se encuentra una falta de coincidencia, el algoritmo asigna el carácter de s1 a s2, es decir, char de s1 como clave y char de s2 como valor se inserta en Hash Map siempre que se produzca una discrepancia.

Después de esto inicialice el resultado como cero.

El siguiente paso es mientras el mapa de hash no esté vacío, haz lo siguiente:

1. Para cualquier clave k encuentra su valor v.
2. Ahora use el valor v como la clave para buscar en el mapa hash para encontrar un valor si el valor encontrado es k, luego incremente el resultado en 1 y elimine ambas claves k y v del mapa hash.
3. Si el valor encontrado no es igual a k, solo elimine la clave k del mapa hash e incremente el resultado.

el resultado mantiene su salida deseada.

Answer 3

Puede construir las cadenas de "diferencia" S y S'' , es decir, una cadena que contiene los caracteres en las diferentes posiciones de las dos cadenas, por ejemplo, para acbacb y abcabc será cbcb y bcbc . Digamos que esto contiene n caracteres.

Ahora puede construir un "gráfico de permutación" G que tendrá n nodos y un borde de i a j si S[i] == S''[j] . En el caso de todos los caracteres únicos, es fácil ver que el número requerido de intercambios será (n - número de ciclos en G), que se puede encontrar en tiempo O (n).

Sin embargo, en el caso de que haya cualquier número de caracteres duplicados, esto reduce el problema de encontrar el mayor número de ciclos en un gráfico dirigido, lo cual, creo, es NP-duro (por ejemplo, consulte: http://www.math.ucsd.edu/~jverstra/dcig.pdf ).

En ese artículo se señalan algunos algoritmos codiciosos, uno de los cuales es particularmente simple:

1. En cada paso, encuentre el ciclo de longitud mínima en el gráfico (por ejemplo, Encuentre el ciclo de longitud más corta en un gráfico dirigido con pesos positivos )
2. Bórralo
3. Repita hasta que no se hayan cubierto todos los vértices.

Sin embargo, puede haber algoritmos eficientes que utilicen las propiedades de su caso (el único en el que puedo pensar es que sus gráficos serán K-partite, donde K es el número de caracteres únicos en S ). ¡Buena suerte!

Edición: consulte la respuesta de David para obtener una explicación más completa y correcta del problema.

Answer 4

Realice una búsqueda A * (consulte http://en.wikipedia.org/wiki/A-star_search_algorithm para obtener una explicación) para obtener la ruta más corta a través del gráfico de cadenas equivalentes de una cadena a la otra. Use la distancia / 2 de Levenshtein como su costo heurístico.