轉換N個字符串，以最大K的共同目標串編輯

我有一組串[S1 S2 S3 ... Sn]的，我來算這樣的總的範圍內的的S1 S2... Sn每一個都可以被轉化爲T所有這樣的目標串TK編輯。
所有的字符串都是固定長度L，這裏的編輯是hamming distance。
轉換N個字符串，以最大K的共同目標串編輯

我只是一種蠻力的方法。所以，如果我的字母大小是4，我已經採樣了O（4^L）的空間，並且花費O（L）時間檢查它們中的每一個。我似乎無法將複雜性從指數級降低到一些聚或僞聚！有什麼方法可以削減樣本空間做得更好？

我試圖將其視爲在L維向量空間中。我已經給出N個點並且必須計算距給定N個點的距離總和小於或等於K的所有點。
i.e. d1 + d2 + d3 +...+ dN <= K
有沒有任何已知的幾何算法可以解決這個問題或類似問題複雜？請點我正確的方向或任何暗示讚賞。
謝謝

來源

2012-02-16 srbhkmr

您可以通過動態編程高效地完成此操作。

的核心思想是，你不必列舉所有可能的目標字符串，你只需要知道有多少種方法目標是可以使用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

來源

2012-02-16 17:00:11

你說得對，那敏銳的觀察力做這項工作。我們需要將它分解爲長度方面的數據，並計算在耗盡我們的K之前可能會創建的字符串。我真的需要用DP n遞歸思考來獲得更好的效果！反正，感謝您的快速幫助。 – srbhkmr 2012-02-16 18:55:04

編輯作業僅考慮字符串indicies大聲思考，在我看來，這個問題歸結爲一個組合問題。對於長度爲L的字符串S，總共有C（L，K）（二項係數）位置可以被替換，因此（ALPHABET_SIZE^K）* C（L，K）目標字符串牛逼從K的海明距離

二項式係數可以很容易地計算出使用動態規劃和帕斯卡三角...沒必要弄瘋到factoriel等等...現在

一個字符串的情況是處理，處理多個字符串有點棘手，因爲你可能會重複計數目標。直觀地說，如果S1離K遠離S2，那麼兩個字符串都會生成相同的目標集合，所以在這種情況下你不會重複計數。最後這句話可能是一個長鏡頭，這就是爲什麼我做了肯定地說「憑直覺」 :)

希望它能幫助，

來源

2012-02-16 17:30:39

轉換N個字符串，以最大K的共同目標串編輯

回答

相關問題