减少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

您正在寻找的是Python中的Quine-McCluskey算法实现.

一个快速谷歌带我到Python的这个SO Page Quine-McCluskey算法