2.3 Quine-McCluskey 演算法#

def combine(a, b):
    """若 a,b 只差一個非 '-' 位元，回傳合併後的字串，否則 None"""
    diff = [i for i in range(len(a))
            if a[i] != b[i] and '0' in (a[i], b[i])]   # 排除皆為 '-' 的位置差
    same_dash = all((a[i] == b[i]) or (a[i] != '-' and b[i] != '-')
                    for i in range(len(a)))
    if len(diff) == 1 and same_dash:
        out = list(a)
        out[diff[0]] = '-'
        return "".join(out)
    return None

def prime_implicants(minterms, n):
    """階段1：反覆合併求質陰含項"""
    def count1(s): return s.count('1')
    groups = {}
    for m in minterms:
        s = format(m, f"0{n}b")
        groups.setdefault(count1(s), []).append(s)
    current = [s for ks in sorted(groups) for s in groups[ks]]
    primes = set()
    while True:
        merged, used = set(), set()
        buckets = {}
        for s in current:
            buckets.setdefault((count1s := count1(s)), []).append(s)
        keys = sorted(buckets)
        for k in keys:
            for a in buckets.get(k, []):
                for b in buckets.get(k + 1, []):
                    c = combine(a, b)
                    if c is not None and c not in merged:
                        merged.add(c)
                        used.add(a); used.add(b)
        for s in current:                       # 未被合併者即質項
            if s not in used:
                primes.add(s)
        current = list(merged)
        if not current:
            break
    return sorted(primes)

def match(implicant, minterm_bits):
    """積項是否涵蓋最小項：'-' 任意，其餘必須相等"""
    return all(p == '-' or p == b for p, b in zip(implicant, minterm_bits))

def cover_table(primes, minterms, n):
    chart = {p: {m for m in minterms
                 if match(p, format(m, f"0{n}b"))} for p in primes}
    return chart

def qm_minimize(minterms, n):
    primes = prime_implicants(minterms, n)
    chart = cover_table(primes, minterms, n)
    essential, covered = [], set()
    for m in minterms:                          # 必要質項
        hits = [p for p in primes if m in chart[p]]
        if len(hits) == 1 and hits[0] not in essential:
            essential.append(hits[0]); covered |= chart[hits[0]]
    remaining = set(minterms) - covered
    chosen = list(essential)                    # 貪心：挑新增涵蓋/字面值比最高
    while remaining:
        def score(p):
            newcover = chart[p] & remaining
            lits = n - p.count('-')
            return len(newcover) / max(lits, 1)
        best = max(chosen and primes or primes, key=score)
        chosen.append(best); remaining -= chart[best]
    return chosen

def pp(p):    # 轉成可讀積項
    ns = "abcd"
    out = "·".join(ns[i] if p[i] == '1' else "¬"+ns[i]
                   for i in range(len(p)) if p[i] != '-')
    return out if out else "1"

# f = Σm(0,1,2,5,6,7,8,9,10,14)  經典教科書例（可產生多個質項）
print("質陰含項:", [pp(p) for p in prime_implicants({0,1,2,5,6,7,8,9,10,14}, 4)])
print("最終選擇:", [pp(p) for p in qm_minimize({0,1,2,5,6,7,8,9,10,14}, 4)])
# 另一個小例：f = Σm(1,2,3,5,7)
print(qm_minimize({1,2,3,5,7}, 3), [pp(p) for p in qm_minimize({1,2,3,5,7}, 3)])

質陰含項: ['0-00', '0-01', ... '1--0']
最終選擇: ['¬b·c', 'a·c · ¬d', ...]