Convertir las cadenas de N a una cadena objetivo común en el máximo de K ediciones

Question

Tengo un conjunto de cadenas [S1 S2 S3 ... Sn] Y debo contar todas esas cadenas objetivo T tal que cada uno de S1 S2... Sn se puede convertir en T dentro de un total de K ediciones.
Todas las cuerdas son de longitud fija L y una edición aquí es distancia de hamming.

Todo lo que tengo es una especie de enfoque de fuerza bruta. Entonces, si mi tamaño de alfabeto es 4, tengo un espacio muestral de o (4^l) y lleva O (l) tiempo verificar cada uno de ellos. ¡Parece que no puedo reducir la complejidad de exponencial a un poli o pseudo-poli! ¿Hay alguna forma de podar por el espacio de la muestra para hacerlo mejor?

Traté de visualizarlo como en un espacio vectorial L-dimensional. Me han dado N puntos y tengo que contar todos los puntos cuya suma de distancia desde los puntos n dados es menor o igual a K.
i.e. d1 + d2 + d3 +...+ dN <= K
¿Hay algún algoritmo geométrico conocido que resuelva este o problema similar con una mejor complejidad? Por favor, apunte en la dirección correcta o se agradecen cualquier pista.
Gracias

Answer 1

Puede hacerlo de manera eficiente con la programación dinámica.

La idea clave es que no necesita enumerar todas las cadenas de objetivos posibles, solo necesita saber de cuántas formas en que los objetivos son posibles con K edits, considerando solo las indicaciones de cadena después de I.

alphabet = 'abcd'
s = [ 'aabbbb', 'bacaaa', 'dabbbb', 'cabaaa']

# use memoized from http://wiki.python.org/moin/PythonDecoratorLibrary          
@memoized
def count(edits_left, index):
  if index == -1 and edits_left >= 0:
    return 1
  if edits_left < 0:
    return 0
  ret = 0
  for char in alphabet:
    edits_used = 0
    for mutate_str in s:
      if mutate_str[index] != char:
        edits_used += 1
    ret += count(edits_left - edits_used, index - 1)
  return ret

Answer 2

Pensando en voz alta, me parece que este problema se reduce a un problema combinatorio.

En general, para una cadena de longitud l, hay un total de posiciones C (l, k) (coeficiente binomial) que pueden ser sustituidos y, por lo tanto, (alfabet_size^k)*c (l, k) cadenas objetivo T de un martillo Distancia de K.

El coeficiente binomial se puede calcular con bastante facilidad utilizando la programación dinámica y el triángulo Pascal ... no es necesario volverse loco en Factoriel, etc.

Ahora que se trata un caso de cadena, tratar con múltiples cuerdas es un poco más complicado ya que puede contar dos objetivos. Sin embargo, intuitivamente si S1 está lejos de S2, ambas cadenas generarán el mismo conjunto de destino para que no cuente en este caso. Esta última declaración podría ser un tiro largo, por eso me aseguré de decir "intuitivamente" :)

Espero eso ayude,