8.1 排列與組合的枚舉#

def next_permutation(a):
    """就地修改 a 為下一個排列；若已是最後一個則回傳 False"""
    n = len(a)
    i = n - 2
    while i >= 0 and a[i] >= a[i + 1]:
        i -= 1
    if i < 0:
        return False
    j = n - 1
    while a[j] <= a[i]:
        j -= 1
    a[i], a[j] = a[j], a[i]
    a[i + 1:] = reversed(a[i + 1:])
    return True

def all_permutations(items):
    a = sorted(items)
    yield tuple(a)
    while next_permutation(a):
        yield tuple(a)

def gosper_next(c):
    """下一個與 c 同樣位元數（同 k）的整數"""
    u = c & -c
    v = u + c
    return v + (((v ^ c) // u) >> 2)

def all_combinations(n, k):
    """以位元集枚舉 C(n,k)：位元 i 為 1 表示選了元素 i"""
    if k == 0:
        yield ()
        return
    c = (1 << k) - 1                      # 最小：低位 k 個 1
    limit = (1 << n)
    while c < limit:
        yield tuple(i for i in range(n) if c & (1 << i))
        c = gosper_next(c)

# 驗證與對照
print("排列:", list(all_permutations([2, 1, 3])))
print("組合 C(5,3):", list(all_combinations(5, 3)))

import itertools
assert set(all_permutations([2, 1, 3])) == set(itertools.permutations([2, 1, 3]))
assert {frozenset(t) for t in all_combinations(5, 3)} == \
       {frozenset(t) for t in itertools.combinations(range(5), 3)}
print("與 itertools 結果一致 ✓")

# 計數公式對照
import math
assert sum(1 for _ in all_combinations(7, 4)) == math.comb(7, 4)
assert sum(1 for _ in all_permutations([1, 2, 3, 4])) == math.factorial(4)
print("枚舉總數與公式一致 ✓")