파이썬으로 구현하는 조합과 순열 총정리

알고리즘 문제를 풀다 보면 "조합", "순열", 그리고 "중복 처리"를 요구하는 경우가 자주 나온다.
이 글에서는 파이썬을 사용해서 조합과 순열의 다양한 경우(총 8가지)를 모두 정리해보았다.

1. 일반 순열

순서가 있고 중복이 안됨 -> [1, 2, 3]중에 2개씩 선택하는 경우
12, 13, 21, 23, 31, 32

✅ DFS를 이용해 직접 구현한 일반 순열

import sys
inp = sys.stdin.readline()

n, m = map(int, inp.split())
arr = []
for i in range(n):
    arr.append(i+1)

result = []
visited = [False]*n

def permut():
    if len(result) == m: 
        print(result)
        return
        
    for i in range(n):
        if visited[i]: continue
        visited[i] = True
        result.append(arr[i])
        permut()
        visited[i] = False
        result.pop()
        
permut()

✅ itertools를 사용해 구현한 일반 순열

from itertools import permutations

data = [1, 2, 3]
result = list(permutations(data, 2))
print(result)

# 출력: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

⏰시간복잡도

O(P(n, m)) = O(n! / (n - m)!)
첫 번째 자리에 n개 중 1개 -> n
두 번째 자리에 n-1개 중 1개 -> n-1
...m개 뽑을 때 까지 곱하면 -> n × (n-1) × ... × (n-m+1) = P(n, m)

---

2. 일반 조합

순서가 없고 중복이 안됨 -> [1, 2, 3]중에 2개씩 선택하는 경우
12, 13, 23

✅ DFS를 이용해 직접 구현한 일반 조합

n, m = map(int, inp.split())
arr = [i+1 for i in range(n)]

result = []
def comb(idx):
    if len(result) == m:
        print(result)
        return

	for i in range(idx, n):
        result.append(arr[i])
        comb(i+1)
        result.pop()

comb(0)

✅ itertools를 사용해 구현한 일반 조합

from itertools import combinations

data = [1, 2, 3]
result = list(combinations(data, 2))
print(result)

# 출력: [(1, 2), (1, 3), (2, 3)]

⏰시간복잡도

O(C(n, m)) = O(n! / (m!(n-m)!))
순열에서 중복되는 값을 없애야 하므로 -> P(n, m) / m!

---

3. 중복 순열

순서가 있고 중복이 가능 -> [1, 2, 3]중에 2개씩 선택하는 경우
11, 12, 13, 21, 22, 23, 31, 32, 33

✅ DFS를 이용해 직접 구현한 중복 순열

n, m = map(int, inp.split())
arr = [i+1 for i in range(n)]

result = []
def dup_permut():
    if len(result) == m:
        print(result)
        return
    
    for i in range(n):
        result.append(arr[i])
        dup_permut()
        result.pop()
        
dup_permut()

✅ itertools를 사용해 구현한 중복 순열

from itertools import product

data = [1, 2, 3]
result = list(product(data, repeat=2))
print(result)

# 출력: [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

⏰시간복잡도

O(n^m)
각 자리마다 n가지를 m번 가능 -> n × n × ... × n = n^m

---

4. 중복 조합

순서가 없고 중복이 가능 -> [1, 2, 3]중에 2개씩 선택하는 경우
11, 12, 13, 22, 23, 33

✅ DFS를 이용해 직접 구현한 중복 조합

n, m = map(int, inp.split())
arr = [i+1 for i in range(n)]
result = []

def dup_comb(idx):
    if len(result) == m:
        print(result)
        return
    
    for i in range(idx, n):
        result.append(arr[i])
        dup_comb(i)
        result.pop()

dup_comb(0)

✅ itertools를 사용해 구현한 중복 조합

from itertools import combinations_with_replacement

data = [1, 2, 3]
result = list(combinations_with_replacement(data, 2))
print(result)

# 출력: [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

⏰시간복잡도

O(C(n + m - 1, m)) = O((n + m - 1)! / (m!(n-1)!))
서로 다른 원소 n개 중 중복을 허용하여 m개 선택 -> 중복 조합 공식 사용
[1,2,3]에서 2개를 중복 허용 조합 → C(3 + 2 - 1, 2) = C(4,2)

---

5. 중복값이 존재하는 일반 순열

순서가 있고 중복값이 존재하는 일반 순열 -> [1, 2, 3, 3]중에 2개를 선택하는 경우
12, 13, 21, 23, 31, 32, 33

✅ DFS를 이용해 직접 구현한 중복값이 존재하는 일반 순열

(※ itertools로는 구현 불가)

m = 2
arr = [1, 2, 3, 3]
result = []
visited = [False]*len(arr)
def dup_num_permut():
    if len(result) == m:
        print(result)
        return
    
    tmp = 0

    for i in range(len(arr)):
        if tmp == arr[i] or visited[i]: continue
    
        result.append(arr[i])
        tmp = arr[i]
        visited[i] = True
        dup_num_permut()
        result.pop()
        visited[i] = False
        
dup_num_permut()

6. 중복값이 존재하는 일반 조합

순서가 없고 중복값이 존재하는 일반 조합 -> [1, 2, 3, 3]중에 2개를 선택하는 경우
12, 13, 23, 33

✅ DFS를 이용해 직접 구현한 중복값이 존재하는 일반 조합

(※ itertools로는 구현 불가)

m = 2
arr = [1, 2, 3, 3]
result = []
def dup_num_comb(idx):
    if len(result) == m:
        print(result)
        return
    
    tmp = 0

    for i in range(idx, len(arr)):
        if tmp == arr[i]: continue
        result.append(arr[i])
        tmp = arr[i]
        dup_num_comb(i+1)
        result.pop()

dup_num_comb(0) 

7. 중복값이 존재하는 중복 순열

순서가 있고 중복 값이 존재하는 중복 순열 -> [1, 2, 3, 3]중에 2개를 선택하는 경우
11, 12, 13, 21, 22, 23, 31, 32, 33

✅ DFS를 이용해 직접 구현한 중복값이 존재하는 중복 순열

(※ itertools로는 구현 불가)

m = 2
arr = [1, 2, 3, 3]
result = []
def ddup_permut():
    if len(result) == m:
        print(result)
        return
    
    tmp = 0
    for i in range(len(arr)):
        if tmp == arr[i]: continue
        result.append(arr[i])
        tmp = arr[i]
        ddup_permut()
        result.pop()
        
ddup_permut()

8. 중복값이 존재하는 중복 조합

순서가 없고 중복 값이 존재하는 중복 조합 -> [1, 2, 3, 3]중에 2개를 선택하는 경우
11, 12, 13, 22, 23, 33

✅ DFS를 이용해 직접 구현한 중복값이 존재하는 중복 조합

(※ itertools로는 구현 불가)

m = 2
arr = [1, 2, 3, 3]
result = []
def ddup_comb(idx):
    if len(result) == m:
        print(result)
        return
    
    tmp = 0
    for i in range(idx, len(arr)):
        if tmp == arr[i]: continue

        result.append(arr[i])
        tmp = arr[i]
        ddup_comb(i)
        result.pop()
        
ddup_comb(0)

⏰시간복잡도

중복 값이 존재하는 경우에 같은 조합/순열과 시간복잡도가 동일하지만 visited, tmp로 걸러주기 때문에 경우의 수 자체는 줄어듦

---

조합과 순열의 분류

중복 허용	순서 고려	종류
❌	✅	일반 순열
❌	❌	일반 조합
✅	✅	중복 순열
✅	❌	중복 조합
❌	✅	중복값이 존재하는 일반 순열
❌	❌	중복값이 존재하는 일반 조합
✅	✅	중복값이 존재하는 중복 순열
✅	❌	중복값이 존재하는 중복 조합

조합과 순열의 핵심 차이

일반 순열/조합 차이
일반 순열은 순서가 존재하기 때문에 for i in range(n)를 사용하는데, 이때 같은 값이 두번 들어가는 것을 방지하기 위해 visited 배열이 필요하다.
일반 조합의 경우는 순서가 없기 때문에 for i in range(idx, n) 처럼 인덱스가 커지는 경우만 존재하기 때문에 visited 배열이 필요 없다.

일반 순열/조합과 중복 순열/조합의 차이
일반은 중복이 허용되지 않기 때문에 일반 순열의 경우는 visited를 이용해서, 일반 조합은 comb(i+1)처럼 현재 인덱스+1한 값을 매개변수로 넣어준다.
중복은 중복이 허용되기 때문에 중복 순열의 경우는 visited 배열을 없애주고, 중복 조합은 comb(i)를 넣어주면 된다.

'중복값이 존재'와 '중복'의 차이
중복값이 존재한다는 건 arr[1, 2, 3, 3]처럼 배열 내 중복 값이 존재한다는 거고, 중복이 가능하다는건 그 배열 내의 요소로 가능한 조합을 뽑을 경우 해당 요소를 여러 번 사용할 수 있다는 것이다.(예: 1을 두 번 사용해서 11을 만들 수 있음)