Algorithme Quine-McCluskey en Python

Question

J'essaye d'écrire le Quine-McCluskey algorithm en python, mais je voulais voir s'il y avait des versions là-bas que je pourrais utiliser à la place. Une recherche google a montré peu de résultats utiles. Je cherche une réduction de carte 4x4, pas 2x2 ou 3x3. Des idées ou des références?

Answer 1

Dans Wikipedia dont vous avez donné le lien, il y a des « liens externes » en bas, parmi lesquels ceux-ci, intéressant relativement à votre projet:

• "Python Implementation by Robert Dick"

  Wouldn » Est-ce que cela répond à votre besoin?

• "Une série de deux articles décrivant l'algorithme (s) mis en œuvre en R:... first article et second article La mise en œuvre de R est exhaustive et offre des solutions complètes et exactes Il traite jusqu'à 20 variables d'entrée"

  Vous pouvez utiliser le langage rpy Python interface en langage R pour exécuter le code R de l'algorithme Quine-McCluskey. Notez qu'il ya une réécriture de RPY: rpy2

  Aussi, pourquoi pas, vous-même écrire un nouveau script Python, en utilisant l'amélioration de l'algorithme effectué par Adrian Dusa en 2007, se situant dans le second article?

Answer 2

def combine(m, n): 
    a = len(m) 
    c = '' 
    count = 0 
    for i in range(a): 
     if(m[i] == n[i]): 
      c += m[i] 
     elif(m[i] != n[i]): 
      c += '-' 
      count += 1 

    if(count > 1): 
     return None 
    else:    
     return c 


def find_prime_implicants(data): 
    newList = list(data) 
    size = len(newList) 
    IM = [] 
    im = [] 
    im2 = [] 
    mark = [0]*size 
    m = 0 
    for i in range(size): 
     for j in range(i+1, size): 
      c = combine(str(newList[i]), str(newList[j])) 
      if c != None: 
       im.append(str(c)) 
       mark[i] = 1 
       mark[j] = 1 
      else: 
       continue 

    mark2 = [0]*len(im) 
    for p in range(len(im)): 
     for n in range(p+1, len(im)): 
      if(p != n and mark2[n] == 0): 
       if(im[p] == im[n]): 
        mark2[n] = 1 


    for r in range(len(im)): 
     if(mark2[r] == 0): 
      im2.append(im[r]) 

    for q in range(size): 
     if(mark[q] == 0): 
      IM.append(str(newList[q])) 
      m = m+1 

    if(m == size or size == 1): 
     return IM 
    else: 
     return IM + find_prime_implicants(im2) 


minterms = set(['1101', '1100', '1110', '1111', '1010', '0011', '0111', '0110']) 

minterms2 = set(['0000', '0100', '1000', '0101', '1100', '0111', '1011', '1111']) 

minterms3 = set(['0001', '0011', '0100', '0110', '1011', '0000', '1000', '1010', '1100', '1101']) 

print 'PI(s):', find_prime_implicants(minterms) 

print 'PI2(s):', find_prime_implicants(minterms2) 

print 'PI3(s):', find_prime_implicants(minterms3)