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.
Where it lands in Jayverse
- Verex: exhaustively enumerate order-state flag combinations in Foundry tests. Instead of sampling, generate every combination of order-state flags (open/partial/cancelled x maker/taker x resolved/unresolved) as branch tests, using the Gray-code/XOR trick as the generator.
- Wallet: exhaustively test session-key/mandate permission combinations. EIP-7702/7715 permission-flag combinations are a small finite space; enumerate them all in tests rather than fuzzing, per the page's own claim that exhaustive coverage beats random fuzzing there.
- Rabbit: use minimal-change ordering in the mandate config test harness. When stepping through option combinations for the Chains menu or mandate config, use Gray-code-style minimal-change ordering so each test state updates incrementally instead of recomputing from scratch.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| from scratch | 처음부터(다시) · "eliminating the cost of recomputing each state from scratch" |
| minimal-change | 한 번에 최소한만 바뀌는(방식) · "minimal-change enumeration" |
| exhaustive search | 전수 탐색, 빠짐없이 다 뒤지는 탐색 · "exhaustive search of small state spaces" |
| rewind (state) | 상태를 되돌리다 · "removes the cost of rewinding state" |
| incrementally | 점진적으로, 조금씩 누적하며 · "computed incrementally from the previous one" |
| with no duplicates and none missed | 중복도 누락도 없이 · "one at a time, with no duplicates and none missed" |
| gives ... a stronger guarantee than | ~보다 더 강한 보장을 준다 · "exhaustive enumeration gives a stronger guarantee than random fuzzing" |
| TAOCP | 커누스의 저서 이름(The Art of Computer Programming) · 이 주제(조합 생성·그레이 코드)의 출처로 언급된 고전. "Permutation Enumeration (TAOCP Vol. 4)" |
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/.