Topswops

Conway의 topswops 게임에서 "가장 오래 걸리는 순열"을 찾는 두 가지 풀이를, Knuth의 CWEB 원본(topswops.w, topswops-fwd.w)과 그것을 옮긴 Go 구현으로 정리한 저장소입니다.

• 참고: Pepperdine, Mathematical Gazette 73 (1989), 131–133.

문제 정의

카드 1..n을 한 줄로 쌓아 둔 순열에서 시작한다. 다음을 반복한다.

1. 맨 위 카드의 값을 k라 하자.
2. k == 1이면 멈춘다.
3. 그렇지 않으면 위에서부터 k장을 통째로 뒤집는다(reverse).

게임은 반드시 유한 번에 끝난다(맨 위가 1이 되면 종료). 한 순열에서 종료까지 걸린 뒤집기 횟수를 그 순열의 스텝 수라 하고,

f(n) = 크기 n의 모든 순열 중 최대 스텝 수

를 구하는 것이 목표다. 알려진 값(OEIS A000375)은 다음과 같다.

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
f(n)	0	1	2	4	7	10	16	22	30	38	51	65	80	101	113	114

예시 (n = 3)

3 1 2   → 맨 위 3, 앞 3장 뒤집기
2 1 3   → 맨 위 2, 앞 2장 뒤집기
1 2 3   → 맨 위 1, 종료 (2 스텝)

3 1 2는 크기 3에서 최대인 2스텝이 걸리므로 f(3) = 2.

flowchart LR
    A["3 1 2"] -->|"맨 위 3 → 앞 3장 뒤집기"| B["2 1 3"]
    B -->|"맨 위 2 → 앞 2장 뒤집기"| C["1 2 3 (종료)"]

Loading

두 가지 풀이

같은 f(n)을 정반대 전략으로 구한다.

Backward — 종료 상태에서 거꾸로 (backward/)

종료 상태(맨 위가 1)에서 출발해, 직전 한 수(forward move)를 한 번에 하나씩 거꾸로 되돌리며 깊이우선으로 순열을 키운다.

• 레벨 l의 순열은 "종료까지 정확히 l 스텝 걸리는" 순열이다.
• "앞 k+1장 뒤집기"를 역으로 풀면, 직전 순열은 맨 위 카드가 k+1이고 위치 0..k가 뒤집힌 모양이다. 이를 모든 가능한 k에 대해 시도하는 DFS다.
• 부분 순열: 게임 중 한 번도 읽히지 않는 위치는 값을 정하지 않고 0(미정)으로 둔다. 사용 여부 비트맵으로 값 중복만 막는다. 덕분에 탐색 공간이 줄어든다.
• 가지치기는 없다. 구조가 단순하지만 n이 커질수록 급격히 느려진다.

도달한 최대 깊이가 곧 f(n)이다.

의사코드 (Backward)

function Backward(n):
    best ← -1
    search(l=0, cur=[1, 0, 0, …, 0], used={})   # 종료 상태: 맨 위가 1
    return best + 1                              # = f(n)

function search(l, cur, used):
    for k in 1 .. n-1:
        # "앞 k+1장 뒤집기"를 되돌릴 수 있는가?
        if cur[k] == 0:                          # 위치 k 미정
            if (k+1) ∈ used: continue            #   값 k+1 이미 사용됨
        else if cur[k] ≠ k+1: continue           # 위치 k 값 불일치 → 불가

        prev ← cur
        prev[1..k] ← cur[k-1 .. 0]               # 위치 0..k 뒤집기(역연산)
        prev[0]   ← k+1                          # 맨 위 = k+1
        best ← max(best, l)                      # prev 는 l+1 스텝 순열
        search(l+1, prev, used ∪ {k+1})

탐색 트리 (역방향)

노드 = 순열, 간선 = 한 수 되돌리기, 깊이 = 스텝 수. 깊어질수록 더 많은 스텝이 걸린다.

flowchart TD
    T["[1 · · ·]  0 스텝 (종료)"]
    T -->|"k=1"| A["[2 1 · ·]  1 스텝"]
    A -->|"k=2"| B["[3 1 2 ·]  2 스텝"]
    A -->|"다른 k"| B2["다른 2 스텝 순열"]
    B -->|"k=3"| C["[4 2 1 3]  3 스텝"]
    B -->|"다른 k"| C2["다른 3 스텝 순열"]
    C -->|"⋯"| D["⋯ 더 깊이"]

Loading

Forward — 앞으로 시뮬레이션 + 분기한정 (forward/)

시작 순열을 미리 정하지 않고 게임을 앞으로 시뮬레이션한다. 아직 정체가 안 정해진 카드(음수 placeholder)가 맨 위에 드러나면 그 값을 무엇으로 할지 분기한다.

• 결정된 부분으로 게임을 끝까지 돌려 스텝 수를 세고, 미결정 카드를 만나면 멈춰 분기한다.
• 후보 배정은 inversion table 기반 genlex(계승진법) 순열 생성으로 중복 없이 열거한다.
• 분기한정(branch-and-bound): 남은 미결정 부분은 더 작은 topswops 부분문제처럼 행동하므로, 거기서 더 나올 수 있는 스텝은 최대 f(m). "지금까지 스텝 + f(m)"이 목표 기록에 못 미치면 그 가지를 즉시 버린다. 이 상한 덕분에 큰 n도 현실적으로 탐색된다.

해를 찾으면 선택 순서로부터 실제 시작 순열을 역산해 출력한다.

의사코드 (Forward)

실제 코드는 inversion table 기반 genlex 생성과 goto로 구현되어 있으나, 핵심 흐름은 다음과 같다.

function Forward(n):
    score ← 알려진 f(0..16)               # 목표(기록)이자 가지치기 상한
    deck  ← [-1, -2, …, -(n-1), 0]        # 음수 = 미결정 placeholder
    explore(l=1, deck, c=0)
    return score[n]                       # = f(n)

function explore(l, deck, c):
    for each 후보 카드값 k (genlex 순서로 열거):
        m ← 남은 미결정 영역의 크기
        if c + score[m] < score[n]: continue   # ── 분기한정: 기록 못 깸 → 가지치기

        deck' ← deck            # 맨 위 미결정 카드를 값 k로 확정
        c'    ← c
        loop:                   # 결정된 부분으로 게임을 진행
            앞 (맨 위 값)장 뒤집기
            if 맨 위가 미결정(≤0): break       #   미결정 카드 만나면 멈춰 분기
            c' ← c' + 1
        if l == n-1:                            # 모든 카드 결정됨(잎)
            if c' ≥ score[n]: score[n] ← c'; 해 기록·출력
        else:
            explore(l+1, deck', c')

제어 흐름 (원본 goto 구조)

원본 topswops-fwd.w(와 Go 포팅)는 위 재귀를 advance / tryit / infeas / backup / nextv 라벨의 상태 기계로 펼쳐 놓았다.

flowchart TD
    init([초기화]) --> advance
    advance["advance: j--"] --> tryit
    tryit{"tryit: 후보 k 선택<br/>실현 가능 & 한계 통과?"}
    tryit -->|아니오| infeas
    tryit -->|예| sim["게임 시뮬레이션<br/>스텝 c 누적"]
    sim --> leaf{"l == n-1 ?"}
    leaf -->|예| rec["c ≥ 기록이면<br/>해 기록·출력"] --> nextv
    leaf -->|아니오| down["레벨 내려감<br/>l++, j=n-l"] --> advance
    infeas{"infeas: j ≠ 0 ?"}
    infeas -->|예| advance
    infeas -->|아니오| backup["backup: l--"]
    backup --> nextv
    nextv{"nextv: 더 시도할 후보?"}
    nextv -->|"있음 (swap 복원)"| tryit
    nextv -->|"v[l]=0 (소진)"| backup
    nextv -->|"없음 & l=0"| done([통계 출력·종료])

Loading

비교

	Backward	Forward
방향	종료에서 역추적 DFS	시작에서 앞방향 시뮬레이션
미정 표현	위치 값 0	덱의 음수 placeholder
가지치기	없음	score[] 상한으로 적극 pruning
순열 생성	DFS 분기	genlex(inversion table)
규모	작은~중간 n	더 큰 n까지 (원본 n=16)

두 방식은 전혀 다른 경로로 같은 f(n)에 도달하므로 서로 좋은 교차 검증이 된다.

디렉토리 구성

.
├── main.go             두 풀이를 같은 n으로 돌려 비교하는 래퍼
├── backward/
│   ├── topswops.go     backward 풀이 데모 (package main, n=15)
│   └── topswops.w      원본 CWEB (backward)
└── forward/
    ├── topswops_fwd.go forward 풀이 데모 (package main, n=16)
    └── topswops-fwd.w  원본 CWEB (forward)

• backward/, forward/는 각자 독립된 package main이라 그대로 실행할 수 있는 데모다.

사용법

데모 직접 실행

go run ./backward     # backward (n=15) — 신기록 순열을 갱신될 때마다 출력
go run ./forward      # forward  (n=16) — 탐색 공간이 방대해 사실상 무한

작은 n으로 보려면 각 파일 상단의 const n 값을 바꾼다.

교차 검증 래퍼

go run .                       # both, n=10
go run . -mode both -n 9       # 두 풀이 결과 비교
go run . -mode forward -n 8 -v # 상세 출력(순열 + 노드 통계)

플래그:

• -mode : backward | forward | both (기본 both)
• -n : 순열 크기 1..16 (기본 10)
• -v : 각 풀이의 전체 출력도 표시

both 모드는 두 결과가 다르면 종료 코드 1을 반환한다. 예시 출력:

$ go run . -mode both -n 8
n=8  backward=22  forward=22  match=true

빌드·검증

go vet .
go build .
for n in 6 7 8 9 10; do go run . -mode both -n $n; done

n = 6..10에서 backward·forward·알려진 f(n)이 모두 일치함을 확인했다.