Lesson 14 of 20

순열 — 순서가 있는 뽑기

줄 세우기, 그리고 팩토리얼의 폭발

학생 5명 중 3명을 뽑아 1등 · 2등 · 3등을 정합니다. 몇 가지일까요?

곱의 법칙을 씁니다. 1등은 5명 중 아무나(5가지), 2등은 남은 4명 중(4가지), 3등은 남은 3명 중(3가지). 5 × 4 × 3 = 60가지.

이렇게 순서를 따져서 뽑는 것을 순열(permutation)이라 하고 P(n, r) 또는 ₙPᵣ 라고 씁니다.

P(n, r) = n × (n−1) × … × (n−r+1) = n! / (n−r)!

여기서 n!(n 팩토리얼)은 1 × 2 × … × n 입니다. 0! = 1로 약속해요 — "아무것도 안 고르는 방법도 한 가지"라는 뜻입니다.

High school순서가 있는 뽑기

순열은 줄 세우기입니다.

n 명을 줄 세우는 방법 = n!

왜 그런가 — 13강의 곱의 법칙

자리	선택지
1번째	n 명 중
2번째	n−1 명 중
…	—
마지막	1

n × (n−1) × … × 1 = n!

일부만 뽑을 때

P(n,r) = n × (n−1) × … × (n−r+1) = n! / (n−r)!

예	계산
10명 중 1·2·3등	10 × 9 × 8 = 720

"등수" 가 있으면 순서가 중요하다 — 순열이다

순서가 중요한지 판단하는 법

물음	답
A,B 와 B,A 가 다른가	다르면 순열
—	같으면 조합 (15강)

비유 — 자물쇠 vs 가방

—	순서
번호 자물쇠 1-2-3	중요하다 — 3-2-1 은 안 열린다
가방에 물건 넣기	상관없다

영어로도 "combination lock" 은 사실 permutation 이다 — 잘못된 이름

itertools.permutations 가 순열을 전부 만들어 줍니다.

Python Runs in your browser

from itertools import permutations
import math

학생 = ["민준", "서연", "지호", "하윤", "예준"]
n, r = len(학생), 3

모든경우 = list(permutations(학생, r))
print("앞의 6가지만 보면:")
for 순서 in 모든경우[:6]:
    print("   1등", 순서[0], "· 2등", 순서[1], "· 3등", 순서[2])
print("   …")
print()
print(f"P({n},{r}) = {n}×{n-1}×{n-2} = {math.perm(n, r)}")
print(f"실제로 센 개수: {len(모든경우)}")

🎮 직접 줄을 세워 보세요

사람 수와 뽑을 수를 바꿔 보세요. 순서를 바꾼 것이 왜 다른 경우인지 목록으로 확인할 수 있습니다. 원형으로 둘러앉는 경우도 함께 세어 줘요.

High school팩토리얼은 지수보다 빠르게 커집니다

note 의 이 경고를 숫자로 느껴 봅시다.

n	2ⁿ	n!
5	32	120
10	1,024	360만
20	100만	2.4×10¹⁸
60	10¹⁸	10⁸² — 우주의 원자 수보다 많다 ⚠

n=20 부터 비교가 안 된다

왜 더 빠른가

—	곱하는 것
2ⁿ	항상 2
n!	점점 커지는 수 ⭐

곱하는 수 자체가 커지니 가속한다

알고리즘에서의 의미

문제	모든 경우	가능한가
도시 10개 순회	360만	가능 ✔
도시 15개	1조	겨우
도시 20개	2.4×10¹⁸	불가능 ⚠

외판원 문제가 어려운 이유가 이것이다

그래서 실무의 태도

n! 이 보이면	—
완전 탐색	포기한다
대신	근사 · 휴리스틱 · DP

"정답" 을 포기하고 "충분히 좋은 답" 을 찾는다

비유 — 카드 섞기

52장 카드의 배열은 52! 가지입니다.

사실	—
52! ≈ 8×10⁶⁷	—
제대로 섞은 카드 배열	인류 역사상 처음일 가능성이 높다 ⭐

경우의 수가 크면 중복이 사실상 없다 — 16강 생일 문제와 대조된다

n!은 2ⁿ보다도 훨씬 빠르게 폭발합니다.

Python Runs in your browser

import math
print(f"{'n':>3}{'n!':>28}{'2^n':>18}")
print("-" * 50)
for n in (5, 10, 15, 20, 25, 30):
    print(f"{n:>3}{math.factorial(n):>28,}{2**n:>18,}")
print()
print("n=20 에서 이미 팩토리얼이 2^n 보다 1000만 배 큽니다.")

같은 것이 있는 순열

MISSISSIPPI 의 글자를 배열하는 방법은 몇 가지일까요? 11글자니까 11!… 이 아닙니다. 같은 글자끼리는 바꿔도 구별이 안 되니까요.

S가 4개, I가 4개, P가 2개 있으므로 중복된 만큼 나눠 줍니다.

11! / (4! × 4! × 2! × 1!) = 34,650

"같은 것을 구별하지 않는다"는 아이디어는 다음 강의 조합의 핵심이기도 합니다.

set() 으로 중복을 없애 세어 보면 공식과 같습니다.

Python Runs in your browser

import math
from collections import Counter

def 같은것순열(말):
    세기 = Counter(말)
    분모 = 1
    for c in 세기.values():
        분모 *= math.factorial(c)
    return math.factorial(len(말)) // 분모, 세기

for 말 in ("MISSISSIPPI", "BANANA", "가나다"):
    답, 세기 = 같은것순열(말)
    print(f"{말:<12} 글자 구성 {dict(세기)}")
    print(f"{'':<12} → {len(말)}! / {'/'.join(f'{c}!' for c in 세기.values())} = {답:,}가지\n")

# 작은 예로 직접 확인
from itertools import permutations
print("BANANA 를 실제로 세면:", len(set(permutations("BANANA"))), "가지")

High school원순열 — 둥근 탁자에 앉기

note 의 이 예가 중복 세기를 다루는 법을 보여 줍니다.

둥근 탁자에서는 회전이 같은 배치다

그래서 나눕니다

—	—
일렬 배치	n!
같은 것으로 세어진 배치	n 가지 (회전)
원순열	n!/n = (n−1)!

중복해서 센 만큼 나눈다 — 세기의 핵심 기술

왜 n 으로 나누나

같은 원형 배치를 어디서 끊어 일렬로 쓰느냐에 따라 n 가지 문자열이 나옵니다.

원형 ABC	일렬로 쓰면
—	ABC · BCA · CAB — 3가지

3! = 6 을 3으로 나누면 2 — 원순열 (3−1)! = 2 ✔

같은 기술이 여러 곳에

상황	나누는 수
원순열	n (회전)
목걸이 (뒤집기도 같다)	2n
조합 (15강)	r! (순서) ⭐
같은 것이 있는 순열	같은 것의 팩토리얼

"몇 번 중복해 세었나" 를 알면 나누면 된다

비유 — 사진 세기

같은 장면을 여러 각도에서 찍었습니다. "몇 장면인가" 를 세려면?

—	—
사진 수 ÷ 장면당 각도 수	장면 수 ✔

"같은 것" 의 기준이 정해지면 나눗셈이 답이다

회전해서 겹치는 것끼리 묶으면 정확히 n으로 나눠집니다.

Python Runs in your browser

import math
n = 5
print(f"{n}명 줄 세우기 : {math.factorial(n)}가지")
print(f"{n}명 원탁 앉기 : {math.factorial(n - 1)}가지  ← 회전한 것은 같은 배치")
print()

# 왜 나누는지 눈으로 보기
from itertools import permutations
사람 = "ABCD"
전체 = list(permutations(사람))
def 정규화(t):                       # A가 맨 앞에 오도록 회전
    i = t.index("A")
    return t[i:] + t[:i]
서로다른_원배치 = {정규화(t) for t in 전체}
print(f"{len(사람)}명 줄 세우기 {len(전체)}가지 → 회전을 같다고 보면 "
      f"{len(서로다른_원배치)}가지 = {len(사람)-1}!")

High school꼭 기억하세요

14강의 정리입니다.

순열 = 순서가 있는 뽑기 — P(n,r) = n!/(n−r)!

기억하는 요령

공식	읽는 법
P(n,r)	n 부터 r 개를 내려가며 곱한다
P(10,3)	10 × 9 × 8

공식보다 "몇 개를 곱하나" 를 기억하는 게 안전하다

0! = 1 인 이유

관점	설명
정의의 일관성	P(n,n) = n!/0! = n! 이 되려면
의미	아무것도 안 배열하는 방법이 1가지

"아무것도 안 하기" 도 한 가지 방법이다 — 7강 공집합과 같은 논리

코드에서

from itertools import permutations
list(permutations([1,2,3]))     # 6가지
list(permutations([1,2,3], 2))  # P(3,2) = 6가지

⚠ 주의	—
n 이 10 넘으면	메모리가 터진다
대책	제너레이터로 하나씩

"전부 만들어 리스트에" 는 n! 개다 — 절대 하지 않는다

그리고 다음 강

순서를 따지지 않으면 어떻게 될까요? r! 로 나눕니다. 그게 15강입니다.

순열을 먼저 배우는 이유 — 조합이 순열에서 나온다

🤔 Check yourself

7명 중 3명을 뽑아 회장 · 부회장 · 총무를 정하는 방법은?

Answer 직책이 다르므로 순서를 따집니다 — P(7,3) = 7 × 6 × 5 = 210가지. 35는 직책 없이 3명만 뽑는 조합 C(7,3)이고, 343은 7³(중복을 허락한 경우)입니다.

🤔 Check yourself

"AABB" 의 글자를 배열하는 서로 다른 방법의 수는?

Answer 4! / (2! × 2!) = 24 / 4 = 6가지입니다 (AABB, ABAB, ABBA, BAAB, BABA, BBAA). 같은 글자끼리 자리를 바꿔도 구별되지 않으므로 중복된 만큼 나눠 줘야 해요.

🤔 Check yourself

6명이 원탁에 둘러앉는 방법의 수는?

Answer (6−1)! = 5! = 120가지입니다. 720(=6!)은 일렬로 세울 때의 수예요. 원탁에서는 모두 한 칸씩 옮겨 앉아도 같은 배치라서 6으로 나눕니다.