03. 세 번째 수업: 순서를 붕괴시키는 평등의 바구니, 조합 (Combination)

앞에서 배운 순열(P) 은 미친 듯이 잔혹한 위계질서의 등수 매기기(1등, 2등, 3등…) 였습니다. 하지만 카지노에서 플러시를 띄우기 위해 제가 쥐고 있는 패 $5$장의 카드에 순위가 있습니까? 1번으로 스페이드 에이스를 뽑든, 5번째 마지막 장으로 맨 끝에 스페이드 에이스를 뽑든, 어차피 내 손바닥 위 덱(Deck) 안에 $5$장의 뭉치 바구니로 들어오기만 하면 똑같은 조합(Combination) 으로 쳐줍니다.

이 위대한 “순서 붕괴, 중복 압축 렌더링 시스템” 을 기하학의 꽃, 조합 (Combination \ $\mathbf{C}$) 이라고 부릅니다.

1. 계급장을 떼고 대표 기믹으로 뽑아라!

미션: 학생 5명 ($A, B, C, D, E$) 중에서 청소 당번을 할 [평등한 노동팀 대표 2명] 을 선발해라!

만약 멍청한 컴퓨터가 이걸 1장에서 배운 등수(순열 $P$) 시스템으로 굴린다면 이런 로그가 뜹니다.

• “첫 번째 당번 $5$명 중 뽑고 셋업! $\times$ 두 번째 당번 $4$명 중 뽑고 셋업!”
• $= \mathbf{_5P_2 = 5 \times 4 = 20 가지!}$

그런데 컴퓨터의 렌더링 어레이(Array) 슬롯을 뜯어보니 환장할 버그가 터져 있습니다.

• $[A, B]$ 페어 렌더링 됨.
• 주루룩 가다가 $[B, A]$ 페어 또 렌더링 됨.
• $[C, E]$ 페어 렌더링 됨. $\rightarrow$ 저 끝에서 $[E, C]$ 페어 또 렌더링 됨.

“야 이 등신 프로그램아! 어차피 청소 구역에서 조장, 부조장 계급 없이 평등한 대표팀인데, $A$ 랑 $B$ 가 같이 손잡고 노예질하나, $B$ 랑 $A$ 가 손잡고 빗자루질하나 똑같은 1개의 사건 시나리오잖아! 왜 똑같은 우주를 두 번 복제해서 카운트(20번) 하고 난리야?!”

2. 중복 오차 프레임 파괴 필터 (나누기 팩토리얼)

이 멍청한 순열의 ‘과잉 뻥튀기 렌더링’ 데이터를 어떻게 압축 제어해야 할까요? 너무 간단합니다. 아까 뽑힌 $\mathbf{2}$명의 인간 쪼가리들이 자기들끼리 그 좁은 슬롯 안에서 자리 바꾸며 난리 치는(순열) “배치 가지 수($\mathbf{2!}$)” 만큼을 통짜로 분모로 깔고 나눠(Divide) 버리면 됩니다!

• $(A, B \ / \ B, A) \rightarrow$ 요 둘이 어차피 자리 바꾸기 $2!$ ($2$가지) 만큼 헛부스럼 치고 있으니 $2$ 개를 아예 하나의 바구니 $1$ 개 묶음으로 취급!
• $(C, E \ / \ E, C) \rightarrow$ 요놈들도 $2!$ 만큼 헛부스럼 치니 통째로 나누기 $\div 2$

궁극의 제어 스위치 조합(C) 공식: 총 20개 노가다 뻥튀기($\mathbf{_5P_2}$) 를 $\div$ 그 2놈이 자기들끼리 자리 스왑질 하는 경우의 수($\mathbf{2!}$) 로 나눠라!

$\mathbf{_5C_2 = \frac{_5P_2}{2!} = \frac{5 \times 4}{2 \times 1} = 10가지!}$ (현실 세계의 진정한 팀 조합 결과!)

이 ‘조합 C’ 를 쓰면 아까 $20$갈래로 무의미하게 터졌던 트리가 절반인 $10$개의 효율적인 코어 파티룸으로 깔끔하게 컴파일 압축됩니다. 우주방위대 $100$명 중 $3$명을 평등한 전사로 뽑아라? $\rightarrow$ 일단 무식하게 순열 치고! $(100 \times 99 \times 98)$ $\div$ 그 3놈들끼리 줄 세워 자리 바꾸는 짓거리 제거해! $(\mathbf{3! = 3 \times 2 \times 1})$ 이것이 인류가 $N$ 갈래로 폭파하는 도박의 멀티버스를 가장 엘레강스하게 압축 제어하는 연산 해킹, 조합 Combination 코드 블록입니다.