Преобразование 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-редактировании, учитывающем только строки, обозначающие после 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

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

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

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

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

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