Convertir des chaînes N à une chaîne de cible en commun au maximum les modifications K

Question

J'ai un ensemble de [S1 S2 S3 ... Sn] chaîne et je dois compter toutes les chaînes cibles T de telle sorte que chacun de S1 S2... Sn peut être converti en T dans un total de modifications de K.
Toutes les chaînes sont de L de longueur fixe et une modification est ici distance de Hamming.

Tout ce que j'ai est une sorte d'approche de la force brute. Donc, si ma taille de l'alphabet est 4, j'ai l'espace échantillon de O (4 ^ L) et prend un temps O (L) le temps de vérifier chacun d'entre eux. Je ne peux pas sembler réduire la complexité de exponentielle à une poly ou pseudo-poly! Est-il possible de élaguer l'espace échantillon à faire mieux?

J'ai essayé de le visualiser comme dans un espace vectoriel L dimensions. On m'a donné des points N et doivent compter tous les points dont la somme de la distance des N points donné est inférieur ou égal à K.
i.e. d1 + d2 + d3 +...+ dN <= K
Y at-il algorithme géométrique connu qui résout ce problème ou similaire avec une meilleure complexité? Point de bien vouloir me dans la bonne direction ou des conseils sont appréciés.
Merci

Answer 1

Vous pouvez faire cela efficacement avec la programmation dynamique.

L'idée principale est que vous n'avez pas besoin d'énumérer toutes les chaînes cibles possibles, vous avez juste besoin de savoir combien de façons cibles sont possibles avec K Les modifications ne considérant que la chaîne indicies après avoir.

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

En pensant à haute voix, il me semble que ce problème se résume à un problème combinatoire.

En général, pour une chaîne S de longueur L, il y a un total de C (L, K) (coefficient binomial) positions qui peut être substitué et, par conséquent (ALPHABET_SIZE ^ K) * C (L, K) de la cible T à partir d'une distance de Hamming de K.

binomiale Coefficient peut être calculé assez facilement en utilisant la programmation dynamique et le Triangle Pascal ... Pas besoin de devenir fou dans factoriel etc ...

Maintenant que un cas de chaîne est traitée, traiter avec de multiples cordes est un peu plus délicat, car vous pourriez doubler les cibles de comptage. Intuitivement mais si S1 est loin de K S2 alors à la fois la chaîne va générer le même ensemble de la cible pour ne pas compter deux fois dans ce cas. Cette dernière affirmation est peut-être un long shot qui est pourquoi je me suis assuré de dire « intuitivement »:)

it helps,