附錄 C：離散數學與程式實作的速查（Python）#

import itertools

def truth_table(expr, vars):
    for vals in itertools.product([0,1], repeat=len(vars)):
        env = dict(zip(vars, vals))
        print(env, '->', expr(env))

# 檢驗 De Morgan：not(P and Q) == (not P) or (not Q)
for p, q in itertools.product([0,1], repeat=2):
    assert (not (p and q)) == (not p or not q)

def powerset(S):
    S = list(S)
    n = len(S)
    return [frozenset(S[i] for i in range(n) if mask>>i & 1)
            for mask in range(2**n)]

print(len(powerset({1,2,3})))  # 8

from math import comb, perm
from itertools import combinations, permutations

print(comb(52,5))       # 2,598,960：德州撲克手牌
print(perm(10,3))       # 720

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)

def hanoi(n, a='A', b='B', c='C'):
    if n:
        hanoi(n-1, a, c, b)
        print(f"{a} -> {c}")
        hanoi(n-1, b, a, c)

# (1+x)^n 係數 = 二項式係數；兌換問題用捲積
from functools import reduce
import numpy as np

def coins_change(coins, upto):
    f = np.zeros(upto+1); f[0] = 1
    for c in coins:                     # 每種硬幣乘上 1+x^c+x^{2c}+...
        for i in range(c, upto+1):
            f[i] += f[i-c]
    return f

print(int(coins_change([1,2,5], 10)[10]))  # 10 元兌法數

import heapq

def dijkstra(adj, s):
    dist = {s: 0}
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')): continue
        for v, w in adj[u]:
            if d + w < dist.get(v, float('inf')):
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# 最小生成樹（Kruskal）
def kruskal(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x
    mst = []
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if find(u) != find(v):
            parent[find(u)] = find(v)
            mst.append((u, v, w))
    return mst

def is_bipartite(adj, n):
    color = [None]*n
    for s in range(n):
        if color[s] is None:
            color[s] = 0
            stack = [s]
            while stack:
                u = stack.pop()
                for v in adj[u]:
                    if color[v] is None:
                        color[v] = color[u]^1; stack.append(v)
                    elif color[v] == color[u]:
                        return False
    return True

def egcd(a, b):
    if b == 0: return (a, 1, 0)
    g, x, y = egcd(b, a % b)
    return (g, y, x - (a//b)*y)

def modinv(a, n):
    g, x, _ = egcd(a % n, n)
    assert g == 1
    return x % n

def is_prime(n):
    if n < 2: return False
    i = 2
    while i*i <= n:
        if n % i == 0: return False
        i += 1
    return True

# pow(base, exp, mod) 內建即快速冪，RSA 核心一行
m, e, d, N = 42, 65537, 12345, 97*101
assert pow(pow(m, e, N), d, N) == m

def order(g, n):
    k, cur = 1, g % n
    while cur != 1:
        cur = cur * g % n; k += 1
    return k

print(order(3, 7))   # 6：3 是模 7 的原根

def run_dfa(delta, start, accept, s):
    q = start
    for ch in s:
        q = delta[(q, ch)]
    return q in accept

# 接受含偶數個 a 的字串
delta = {(0,'a'):1, (0,'b'):0, (1,'a'):0, (1,'b'):1}
assert run_dfa(delta, 0, {0}, "abba")
assert not run_dfa(delta, 0, {0}, "ab")