最小ハミング距離

私は数日前にPython 3を学習し始めました。コードが悪い場合は謝ります。最小ハミング距離

文字列をリスト内に最小限にしてHamming distanceを見つけるスクリプトを作成しました。今では私が使用する文字列は同じ長さのバイナリワードですので、私の最初の質問はこれをPythonのビットワイズの解決策ですか？

第2に、私のコードは正しいですか？もしそうなら、効率を高める最も良い方法は何ですか？私の検索ではPython 3の回答が返ってこなかったので、ここで質問します。

def min_ham_dist(a): 
    min_dist = len(a[0]) # Defaults minimum distance to maximum length of string. 
    for i in range(len(a)): 
     for j in range(i+1, len(a)): # Compares all words after ith word. 
      dist = 0 
      for k in range(len(a[i])): 
       if a[i][k] != a[j][k]: 
        dist += 1    
      if dist < min_dist: 
       min_dist = dist 
    return min_dist

感謝

出典

2017-03-04 Necessary

整数は任意の長さですか？または彼らは最大の長さを持っていますか？ –

この場合、それらは固定されています。私はこれを書いて、かなり単純な問題を解決するために、長さ12の16バイナリ語のリストを見ました。それは視力で解決されるはずでしたが、人間の誤りを減らすためにスクリプトが最適であると感じました。しかし、任意の長さに適用可能なスクリプトを見てうれしいです。 – Necessary

このwikipediaのページには、素敵で簡潔なPython 3の例があります;）これは基本的にあなたがこの作業をするために必要なものを示しています：2つの入力文字列が同じ長さであればそれらを圧縮するために 'zip（） zipの中で、どれくらい多くが不等であるかを数えます。 – Dartmouth

また、このためにscipyのダウンロード（PDIST）を使用できますが、2次元配列への入力を変更する必要があります。それは分数としてハミング距離を返します。このためには、数値の文字列が必要です（バイナリ文字列は大丈夫です）。

from scipy.spatial.distance import pdist 

def min_ham_dist(a): 
    return min(pdist([list(i) for i in a], 'hamming'))*len(a[0])

出典

2017-03-04 22:01:15 scienceisthenewblack

答えて

関連する問題