6

プログラミング演習の観点からでも、やや興味深い問題だと思うものがあります。

ユーザーに提示するために、よりコンパクトな形式に縮小したいバイナリ パターンの長いリストがあります。従うべき表記法は、「-」は「1」または「0」のいずれかを表すことができるため、および['1011','1010']で表すことができるということです 。['101-']

['1100', '1000', '0100', '0000', '1111', '1011', '0111', '0011']

で表すことができます['--00', '--11']。すべてのパターンは常に同じ長さであることに注意してください (ただし、4 ビットよりも長い可能性があります)。

パターンを拡張するのは簡単ですが、縮小するのは少し面倒です。

これを実現するコードを思いつきましたが、長くて遅く、読みにくいものです。

def reducePatterns(patterns):
    '''Reduce patterns into compact dash notation'''
    newPatterns = []  #reduced patterns
    matched = []      #indexes with a string that was already matched
    for x,p1 in enumerate(patterns):    #pattern1
        if x in matched: continue       #skip if this pattern has already been matched
        for y,p2 in enumerate(patterns[x+1:],1):
            if x+y in matched: continue #skip if this pattern has already been matched
            diffs=0     # number of differences found
            for idx,bit in enumerate(zip(p1,p2)):
                if bit[0] != bit [1]:     #count the number of bits that a different
                    diffs += 1
                    dbit  = idx
                if diffs >1:break
            if diffs ==1:   #if exactly 1 bit is different between the two, they can be compressed together
                newPatterns.append(p1[:dbit]+'-'+p1[dbit+1:])
                matched+=[x,x+y]
                break
        if x not in matched: newPatterns.append(p1) #if the pattern wasn't matched, just append it as is.

    if matched:         #if reductions occured on this run, then call again to check if more are possible.
        newPatterns = reducePatterns(newPatterns)

    return newPatterns

これを行うためのより良い/より効率的な方法について提案がある人はいますか? より効果的なループ/イテレータの使用? 正規表現の魔法？私が見逃していたビット単位の操作パッケージはありますか? 少なくとももう少し読みやすいものはありますか？

4

2 に答える 2

5

あなたが探しているのは、Python での Quine–McCluskey アルゴリズムの実装です。

簡単なグーグルでこのSOページに行きました PythonのQuine-McCluskeyアルゴリズム

于 2013-02-13T19:17:08.860 に答える
1

私はこれを徹底的にテストしていませんが (おそらくあまり効率的ではない方法で再帰を使用しています)、動作しているようで、少なくとも「より読みやすい」基準を満たしています。

from itertools import combinations

def collapse(binaries):
    result = set(binaries)
    for b1, b2 in combinations(result, 2): 
        for i in range(len(b1)):
            if b1[:i] + b1[i+1:] == b2[:i] + b2[i+1:]:
                merged = "-".join([b1[:i], b1[i+1:]])
                return sorted(collapse(result ^ {b1, b2, merged}))
    return sorted(result)

例:

>>> collapse(['1100', '1000', '0100', '0000', '1111', '1011', '0111', '0011'])
['--00', '--11']

>>> collapse(["00", "01", "10", "11"])
['--']

>>> collapse(["011", "101", "111"])
['-11', '101']
于 2013-02-13T20:22:09.100 に答える