Combinatorial Generation, Gray Codes, and Permutation Enumeration (TAOCP Vol. 4) TODO
Concept
Enumerating combinatorial objects means generating structures like subsets, combinations, or permutations one at a time, with no duplicates and none missed. A Gray code lists subsets so that any two consecutive codes differ in exactly one bit; the reflected binary Gray code is obtained simply by XORing index i with i shifted right by one. Permutations can be enumerated by producing the next permutation in lexicographic order, or by a method that swaps only two adjacent elements at each step to generate every permutation. The key benefit of this kind of minimal-change enumeration is that each next state's value can be computed incrementally from the previous one with a single small update. So the design goal isn't the cost of enumeration itself, but eliminating the cost of recomputing each state from scratch.
In test-vector generation, fuzzing-seed design, and exhaustive search of small state spaces, covering everything without duplication or omission is exactly what gives verification its confidence, and minimal-change ordering removes the cost of rewinding state.
Code & Formula
# 조합 생성·그레이 코드 — 반사 이진 그레이 코드를 생성하고 인접 코드의 해밍 거리가 항상 1임을 검증한다.
def gray_code(n):
return [i ^ (i >> 1) for i in range(1 << n)] # i와 i>>1의 XOR
def hamming_distance(a, b):
return bin(a ^ b).count("1")
def to_bits(x, n):
return format(x, f"0{n}b")
n = 4
codes = gray_code(n)
# 인접 코드가 정확히 1비트만 다른지 검증 (원형으로 마지막→처음도 포함)
distances = [hamming_distance(codes[i], codes[(i + 1) % len(codes)]) for i in range(len(codes))]
assert all(d == 1 for d in distances), "그레이 코드 인접 거리 위반!"
# 그레이 코드 순서로 만든 부분집합과 단순 이진 카운팅 순서로 만든 부분집합이
# "집합으로서는" 동일한지 확인 (순서만 다르고 원소 전체는 같아야 함)
binary_order = list(range(1 << n))
assert set(codes) == set(binary_order)
print(f"n={n} 그레이 코드 ({len(codes)}개):")
for i, c in enumerate(codes):
prev_dist = distances[i - 1] if i else distances[-1]
print(f" step {i:2d}: {to_bits(c, n)} (직전과 해밍거리={prev_dist})")
print("모든 인접 쌍의 해밍 거리 == 1:", all(d == 1 for d in distances))
print("이진 카운팅과 원소 집합 동일:", set(codes) == set(binary_order))
docs/code/algorithms/algorithms-18.py
Exercise
Generate an n-bit Gray code using the XOR formula and unit-test that the Hamming distance between adjacent codes is always 1; then confirm that the same set of subsets, generated instead by plain binary counting, matches it as a set.
Practical Connection
For logic with a small, finite number of conditions or permission-flag combinations, like settlement logic, exhaustive enumeration gives a stronger guarantee than random fuzzing — combinatorial enumeration becomes a practical tool for writing branch tests for smart contracts.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.