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

これは、動的なプログラミングで効率的に行うことができます。

重要なアイデアは、すべての可能なターゲット文字列を列挙する必要がないということです。IIの後の文字列の指標のみを考慮して、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

大声で考えると、この問題は組み合わせの問題に要約されているように思えます。

一般に、長さlの文字列sの場合、置換できるc（l、k）（二項係数）位置があり、したがって（alphabet_size^k）*c（l、k）ターゲット文字列tがハミングからターゲットされています。 Kの距離。

二項係数は、動的プログラミングとPascal Triangleを使用して非常に簡単に計算できます... Factorielなどに夢中になる必要はありません...

1つの文字列ケースが扱われたので、複数の文字列を扱うことは、ターゲットを二重にカウントする可能性があるため、もう少し注意が必要です。直感的には、S1がS2から遠く離れている場合、両方の文字列が同じターゲットのセットを生成するため、この場合は二重カウントされません。この最後の声明はロングショットかもしれないので、私は「直感的に」と言うようにしました:)

それが役に立てば幸い、