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 算法实现。

一个快速的谷歌将我带到了 Python 中的这个 SO Page 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 回答