Python

Question

'de ikili desenlerin azaltılması Sadece bir programlama alıştırması açısından bile, biraz ilginç bir sorun olduğunu düşünüyorum.

Kullanıcılara sunmak için daha kompakt bir biçime küçültmek istediğim uzun bir ikili desenler listemiz var. '-' temsil eder, ya çok ['1011','1010']['101-'] ve

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

ile temsil edilebilir bir '1' ya da '0' ['--00', '--11'] ile temsil edilebilir izlenecek gösterimde bir olmasıdır. Not, tüm desenler her zaman aynı uzunluktadır (ancak 4 bitten daha uzun olabilir).

Desenleri genişletmek oldukça önemsiz, onları azaltmak biraz daha zordur.

Bunu başaran bir kod buldum, ancak uzun, yavaş ve okunması zor bir şey.

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 

Bunu yapmanın daha iyi/daha verimli bir yolu için önerileri olan var mı? Daha etkili döngü/yineleyici kullanımı? Regex büyüsü mü? Bazı bitsel manipülasyon paketini kaçırdım mı? En azından biraz daha okunabilir bir şey?

Answer 1

Aradığınız şey Python'da Quine–McCluskey algorithm uygulamasıdır.

Hızlı google iyice bu test değil (ve bir olasılıkla-çok verimli şekilde değil yineleme kullandığında) de, ancak işe görünüyor ve bu SO Sayfa Quine-McCluskey algorithm in Python

Answer 2

götürdü

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) 

Örnekler: azından "daha okunabilir" kriterini karşılayan

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

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

>>> collapse(["011", "101", "111"]) 
['-11', '101']