Преобразование n строк в общую целевую строку максимум в k редактирования

Question

У меня набор строки [S1 S2 S3 ... Sn] И я должен сосчитать все такие целевые строки T так что каждый из S1 S2... Sn может быть преобразован в T в общей сложности K редактирование.
Все строки имеют фиксированную длину L И редактирование здесь Расстояние Хэминга.

Все, что я, это своего рода подход грубой силы. Итак, если мой размер алфавита 4, я образец пространства O (4^l), и для проверки каждого из них требуется время O (L). Кажется, я не могу преодолеть сложность от экспоненциальной до какой-то поли или псевдополи! Есть ли способ обрезать пространство с образцом, чтобы сделать лучше?

Я попытался визуализировать его, как в L-измерном векторном пространстве. Мне дали n точек, и мне пришлось подсчитать все точки, сумма расстояния от данных N точек меньше или равна K.
i.e. d1 + d2 + d3 +...+ dN <= K
Есть ли какой -либо известный геометрический алгоритм, который решает эту или похожую проблему с лучшей сложностью? Пожалуйста, укажите мне в правильном направлении или любые подсказки ценится.
Спасибо

Answer 1

Вы можете сделать это эффективно с динамическим программированием.

Ключевая идея состоит в том, что вам не нужно перечислять все возможные целевые строки, вам просто нужно знать, сколько способов целей возможна с помощью k редактирования, учитывая только указатели строки после.

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

Думая вслух, мне кажется, что эта проблема сводится к комбинаторной проблеме.

В целом для строки S длины L существует в общей сложности положения C (l, k) (биномиальный коэффициент), которые могут быть заменены и, следовательно Расстояние К.

Биномиальный коэффициент может быть достаточно легко рассчитан с помощью динамического программирования и треугольника Паскаля ... нет необходимости сходить с ума в фактор и т. Д.

Теперь, когда рассматривается один из строковых корпусов, дело с несколькими струнами немного сложнее, так как вы можете дважды считать цели. Интуитивно, хотя, если S1 находится K далеко от S2, то обе строки будут генерировать один и тот же набор цели, так что вы не учитываете в этом случае. Это последнее заявление может быть длинным выстрелом, поэтому я позаботился о том, чтобы сказать «интуитивно» :)

Надеюсь, поможет,