文字列[S1 S2 S3 ... Sn]があります。のすべてをTK編集。
すべての弦は固定長のLで、ここでの編集はhamming distanceです。
N個の文字列を最大K個の編集で共通のターゲット文字列に変換する
すべて私はブルートフォースアプローチの一種です。 私のアルファベットサイズが4の場合、私はO（4^L）のサンプル空間を持っており、O（L）の時間がかかっています。私は指数関数からいくつかのポリまたは疑似ポリに複雑さを引きずることはできません！サンプル空間を整理してよりうまくいく方法はありますか？
L次元のベクトル空間のように視覚化しようとしました。私はN点を与えられており、与えられたN点からの距離の合計がK以下であるすべての点を数えなければならない。i.e. d1 + d2 + d3 +...+ dN <= K
この問題または同様の問題をより良く解決する既知の幾何学アルゴリズム複雑？親切に私を正しい方向に向けるか、どんなヒントもありがとうございます。
ありがとう
これは動的プログラミングで効率的に行うことができます。
キーアイデアは、あなたが可能なすべてのターゲット文字列を列挙する必要がないということです、あなただけのターゲットが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
後にのみ、文字列なインデックスを考慮編集大声で考えてみると、この問題はコンビナトリアルな問題に帰結しているようです。
一般に、長さLのストリングSの場合、置換可能な合計C（L、K）（2項係数）位置が存在するため、（ALPHABET_SIZE^K）* C K.のハミング距離からのTは
は今...動的計画法とパスカルトライアングル... factorielなどに狂気を取得する必要はありませんを使用して非常に簡単に計算できる1つの文字列の場合は、
二項係数である こと複数の文字列を扱うことは、2倍の数のターゲットを使用する可能性があるため、やや難解です。直観的には、S1がKからS2から遠い場合、両方の文字列が同じターゲットセットを生成するため、この場合は2倍にカウントしません。この最後の文は、私が「直感的に」と言って確認しました理由ですロングショットかもしれません:)
それは鋭い観察が仕事をしていることを、あなたが正しい
、お役に立てば幸いです。私たちは長さを分解し、Kを使い果たす前に可能な文字列を数える必要があります。 私はDP nの再帰的思考をより良くする必要があります！とにかく、あなたの急いで助けてくれてありがとう。 – srbhkmr