andy0130tw
3/31/2017 - 8:05 PM

## An (almost functional and pythonic) implementation of Quine–McCluskey algorithm in Python 3.

An (almost functional and pythonic) implementation of Quine–McCluskey algorithm in Python 3.

``````#!/usr/bin/env python3
import sys
from pprint import PrettyPrinter
from os import fstat
from stat import S_ISFIFO, S_ISREG
from itertools import product

_pp = PrettyPrinter(indent=2).pprint
_is_terminal = all(not f(fstat(0).st_mode) for f in [S_ISFIFO, S_ISREG])

def _print_color(*args, **kwargs):
print('\033[04m', *args, '\033[0m', sep='')

if not _is_terminal: _print_color(str)
return str

def to_binary(x, fill):
return bin(x)[2:].zfill(fill)

def count_one(x):
return x.count('1')

def try_merge(x, y):
# Thanks @YuRen-tw for improving this function
mer = ''.join((a if a == b else
('x' if a != '-' and b != '-' else 'e'))
for a, b in zip(x, y))
return mer.replace('x', '-') if (mer.count('x') <= 1 and
mer.count('e') == 0) else None

def term_expr(x):
return ''.join([
chr(i + ord('a'))        if c == '1'
else chr(i + ord('a')) + '\'' if c == '0'
else ''
for i, c in enumerate(x) ])

def input_expr(inp):
return ' + '.join([term_expr(to_binary(k, nvar)) for k in inp])

def set_cover(instance):
# returns a list of minimal number of terms
len_inst = len(instance)
len_vert = len(instance[0])
pick_opti = len_inst
sol_set = []

# states are encoded as inverted bitsets
state_acc = (1 << len_vert) - 1

def __recur(depth, pick_cnt, pick, state):
nonlocal pick_opti
print('depth',  depth,
'picked', pick_cnt,
'state',  to_binary(state, len_vert)[::-1])
if state == state_acc:
print('Covered all implicants with {} terms ({})!'.format(
pick_cnt, to_binary(pick, len_inst)[::-1]))
win = pick_opti - pick_cnt
if win > 0:
sol_set.clear()
if win >= 0:
pick_opti = pick_cnt
sol_set.append(to_binary(pick, len_inst))
return
# prune
if depth == len_inst or pick_cnt == pick_opti: return
# pick and cover
state_add = sum([1 << i for i, k in enumerate(instance[depth]) if k])
__recur(depth + 1, pick_cnt,     pick             , state            )
__recur(depth + 1, pick_cnt + 1, pick | 1 << depth, state | state_add)

__recur(0, 0, 0, 0)
sol_opti = (list(k) for k in (k[::-1] for k in sol_set))
return [[p for p, k in enumerate(x) if k == '1'] for x in sol_opti]

def solver(nvar, one_term, dc_term):
all_term = sorted(one_term + dc_term)

bucket = [{} for _ in range(nvar + 1)]
for i in all_term:
tbin = to_binary(i, nvar)
zcube = {i}
bucket[count_one(tbin)][tbin] = zcube

while True:
ok = True
# XXX: wasting memory
rm_term = [set() for _ in range(len(bucket))]
# XXX: to be more functional
for i in range(len(bucket) - 1):
this_bucket, next_bucket = bucket[i], bucket[i + 1]
print('Merging bucket #{}'.format(i))
for a, b in product(this_bucket, next_bucket):
mer = try_merge(a, b)
if mer is None: continue
print('  {} | {} -> {}; merge {} with {}'.format(
a, b, mer, this_bucket[a], next_bucket[b]
))
# mark to delete
if mer not in this_bucket:
this_bucket[mer] = this_bucket[a] | next_bucket[b]
ok = False
for x in rm_term[i]:
print('  remove {}'.format(x))
del this_bucket[x]
for x in rm_term[-1]:
del bucket[-1][x]
_pp(bucket)
print()
if ok: break
print('NEXT ITERATION ---------------------------------')

terms = [ kv for d in bucket for kv in d.items() ]
print('implicants -------------------------------------')
_pp(terms)

sat = [[int(i in v) for i in one_term] for k, v in terms]
print('set covering instance --------------------------')
print(list(str(x).rjust(2) for x in one_term))
for row in sat:
_pp([ 'xx' if k else '  ' for k in row])

# do set covering on `sat` and convert every possible result in `term_expr`
if sat:
sol_set = set_cover(sat)
ans = [' + '.join([term_expr(terms[idx][0]) for idx in sol])
for sol in sol_set]

print()
print('SOLVED -----------------------------------------')
sat_opti = len(sol_set[0])
print('Simplifing \033[01m\033[34m\u03a3m({}) + \u03a3d({})\033[0m'
.format(input_expr(one_term), input_expr(dc_term)));
print('With \033[01m{}\033[0m term(s) optimially...'.format(sat_opti));

for rec in ans:
print(rec or '[T]')

else:
print()
print('UNSATISFABLE!! ---------------------------------')

if __name__ == '__main__':
try:
print('Number of variables [2-10]: ', end='', flush=True)
if nvar < 2: abort()
npower = 2 ** nvar
except:
print('[END]')
exit(0)

print('Minterms (0..{}): '.format(npower - 1), end='', flush=True)
one_term = [int(_) for _ in readline().split(' ') if _]

print('Don\'t care terms (0..{}): '.format(npower - 1), end='', flush=True)
dc_term = [int(_) for _ in readline().split(' ') if _]
solver(nvar, one_term, dc_term)
``````

# Quine–McCluskey algorithm

-- an almost functional and pythonic implementation (can be refined even more if not being a homework of CSIE-DSDL 2017).

# Test input

``````4
4 8 10 11 12 15
9 14
``````

# Test output

``````Simplifing Σm(a'bc'd' + ab'c'd' + ab'cd' + ab'cd + abc'd' + abcd) + Σd(ab'c'd + abcd')
With 3 term(s) optimially...
ab' + bc'd' + ac
``````

# Outline of debugging message (test input)

``````Number of variables [2-10]: 4
Minterms (0..15): 4 8 10 11 12 15
Don't care terms (0..15): 9 14
Merging bucket #0
Merging bucket #1
0100 | 1100 -> -100; merge {4} with {12}
1000 | 1100 -> 1-00; merge {8} with {12}
1000 | 1001 -> 100-; merge {8} with {9}
1000 | 1010 -> 10-0; merge {8} with {10}
remove 0100
remove 1000
Merging bucket #2
1100 | 1110 -> 11-0; merge {12} with {14}
1001 | 1011 -> 10-1; merge {9} with {11}
1010 | 1110 -> 1-10; merge {10} with {14}
1010 | 1011 -> 101-; merge {10} with {11}
remove 1001
remove 1100
remove 1010
Merging bucket #3
1110 | 1111 -> 111-; merge {14} with {15}
1011 | 1111 -> 1-11; merge {11} with {15}
remove 1110
remove 1011
[ {},
{'-100': {4, 12}, '1-00': {8, 12}, '10-0': {8, 10}, '100-': {8, 9}},
{'1-10': {10, 14}, '10-1': {9, 11}, '101-': {10, 11}, '11-0': {12, 14}},
{'1-11': {11, 15}, '111-': {14, 15}},
{}]

NEXT ITERATION ---------------------------------
...

implicants -------------------------------------
[ ('10--', {8, 9, 10, 11}),
('1--0', {8, 10, 12, 14}),
('-100', {4, 12}),
('1-1-', {10, 11, 14, 15})]
set covering instance --------------------------
[' 4', ' 8', '10', '11', '12', '15']
['  ', 'xx', 'xx', 'xx', '  ', '  ']
['  ', 'xx', 'xx', '  ', 'xx', '  ']
['xx', '  ', '  ', '  ', 'xx', '  ']
['  ', '  ', 'xx', 'xx', '  ', 'xx']
depth 0 picked 0 state 000000
depth 1 picked 0 state 000000
depth 2 picked 0 state 000000
depth 3 picked 0 state 000000
...
Covered all implicants with 3 terms (0111)!
...

SOLVED -----------------------------------------
Simplifing ...
``````