Преобразование n строк в общую целевую строку максимум в k редактирования
-
26-10-2019 - |
Вопрос
У меня набор строки [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
Есть ли какой -либо известный геометрический алгоритм, который решает эту или похожую проблему с лучшей сложностью? Пожалуйста, укажите мне в правильном направлении или любые подсказки ценится.
Спасибо
Решение
Вы можете сделать это эффективно с динамическим программированием.
Ключевая идея состоит в том, что вам не нужно перечислять все возможные целевые строки, вам просто нужно знать, сколько способов целей возможна с помощью 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
Другие советы
Думая вслух, мне кажется, что эта проблема сводится к комбинаторной проблеме.
В целом для строки S длины L существует в общей сложности положения C (l, k) (биномиальный коэффициент), которые могут быть заменены и, следовательно Расстояние К.
Биномиальный коэффициент может быть достаточно легко рассчитан с помощью динамического программирования и треугольника Паскаля ... нет необходимости сходить с ума в фактор и т. Д.
Теперь, когда рассматривается один из строковых корпусов, дело с несколькими струнами немного сложнее, так как вы можете дважды считать цели. Интуитивно, хотя, если S1 находится K далеко от S2, то обе строки будут генерировать один и тот же набор цели, так что вы не учитываете в этом случае. Это последнее заявление может быть длинным выстрелом, поэтому я позаботился о том, чтобы сказать «интуитивно» :)
Надеюсь, поможет,