Преобразование N строк в общую целевую строку максимум за K правок - PullRequest
Новая
       30

Преобразование N строк в общую целевую строку максимум за K правок

2 голосов
/ 16 февраля 2012

У меня есть набор строк [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
Существует ли какой-либо известный геометрический алгоритм, который решает эту или аналогичную проблему с большей сложностью? Пожалуйста, укажите мне в правильном направлении, или любые советы приветствуются.
Спасибо

Ответы [ 2 ]

1 голос
/ 16 февраля 2012

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

Ключевая идея заключается в том, что вам не нужно перечислять все возможные целевые строки, вам просто нужно знать, как много возможных целей с 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
0 голосов
/ 16 февраля 2012

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

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

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

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

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

...