Conversione di N stringhe in una stringa obiettivo comune nel massimo di modifiche K

Question

Ho una serie di [S1 S2 S3 ... Sn] corda e io sono a contare tutti tali stringhe di destinazione T in modo tale che ognuno di S1 S2... Sn può essere convertito in T all'interno di un totale di modifiche K. impara tutte le stringhe sono di L lunghezza fissa e una modifica ecco distanza di Hamming .

tutto quello che ho è una sorta di approccio forza bruta. così, se il mio numero alfabeto è 4, non ho spazio campionario di O (4 ^ L) e ci vuole O (L) tempo di controllare ognuno di loro. Io non riesco a far cadere la complessità da esponenziale a qualche poli o pseudo-poli! C'è un modo per potare giù lo spazio campionario di fare meglio?

Ho cercato di visualizzarlo come in uno spazio vettoriale L-dimensionale. Ho dato N punti e devono contare tutti i punti la cui somma di distanza dai dati punti N è inferiore o uguale a K.
i.e. d1 + d2 + d3 +...+ dN <= K
Esiste un algoritmo geometrico noto che risolve questo o problema simile con una complessità migliore? Gentilmente mi punto nella giusta direzione o eventuali suggerimenti sono apprezzati.
Grazie

Answer 1

Si può fare questo in modo efficace con la programmazione dinamica.

L'idea chiave è che non è necessario enumerare tutte le possibili stringhe di destinazione, è solo bisogno di sapere quanti modi gli obiettivi sono possibili con K che qualsiasi modifica considerando solo le indicies stringa dopo che ho.

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 ad alta voce, mi sembra che questo problema si riduce a un problema combinatorio.

In generale per una stringa S di lunghezza L, ci sono un totale di C (L, K) (coefficiente binomiale) posizioni che può essere sostituito e quindi (ALPHABET_SIZE ^ K) * C (L, K) porta stringhe T da una distanza di Hamming di K.

binomiale coefficiente può essere calcolata facilmente usando Programmazione Dinamica e il Pascal Triangolo ... Non c'è bisogno di impazzire in factoriel ecc ...

Ora che un caso stringa viene trattato, si occupano di più stringhe è un po 'più difficile in quanto si potrebbe raddoppiare gli obiettivi di conteggio. Intuitivamente però se S1 è K lontano da S2 allora sia stringa genererà lo stesso insieme di destinazione in modo da non fare doppio conteggio in questo caso. Quest'ultima affermazione potrebbe essere un campo lungo per questo che ho fatto in modo di dire "intuitivamente":)

Speranza che aiuta,