python - 减少 Python 中的二进制模式

Question

我遇到了一个我认为有点有趣的问题，即使只是从编程练习的角度来看也是如此。

我有一长串二进制模式，我想将其简化为更紧凑的形式以呈现给用户。要遵循的符号是“-”可以表示“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

有没有人对更好/更有效的方法提出建议？更有效的循环/使用迭代器？正则表达式魔法？我遗漏了一些按位操作包？至少有一点可读性？

Answer 1

您要找的是Quine–McCluskey algorithm Python 中的实现。

Google 快速将我带到了这个 SO 页面 Quine-McCluskey algorithm in Python