반응형
0. 조합과 순열을 Python으로 구현해보자!
알고리즘 문제를 풀다보면 종종 조합이나 순열을 사용하는 경우가 생깁니다.
Python에 내장된 itertools 패키지의 combinations와 permutations 모듈을 사용하면 조합과 순열을 쉽게 구할 수 있습니다. 편리하게 자주 쓰는 만큼 한번쯤 구현해보는 게 좋을 것 같아 글을 쓰게 되었습니다.
1. itertools 패키지를 이용한 순열과 조합
itertools 패키지를 이용하여 순열과 조합을 구하는 방법은 간단하여 아래 코드를 보시면 쉽게 파악이 가능할 것 같습니다.
from itertools import combinations, permutations
arr = [1, 2, 3]
# 조합
print(list(combinations(arr, 2)))
# [(1, 2), (1, 3), (2, 3)]
# 순열
print(list(permutations(arr, 2)))
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]2. 재귀함수를 이용해 구현한 순열과 조합
순열과 조합을 재귀적으로 구현할 때 필요한 기본적인 아이디어는 아래와 같습니다.
조합
- combination([0,1,2,3], 2) = ([0], combination([1, 2, 3], 1)) +
([1], combination([2, 3], 1)) +
([2], combination([3], 1)))
def combination(arr, n):
result = []
if n == 0:
return [[]]
for i in range(len(arr)):
elem = arr[i]
for rest in combination(arr[i + 1:], n - 1):
result.append([elem] + rest)
return result
print(combination([0,1,2,3], 2))
# [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]순열
- permutation([0,1,2,3], 2) = ([0], permutation([1, 2, 3], 1)) +
([1], permutation([0, 2, 3], 1)) +
([2], permutation([0, 1, 3], 1)) +
([3], permutation([0, 1, 2], 1))
def permutation(arr, n):
result = []
if n == 0:
return [[]]
for i in range(len(arr)):
elem = arr[i]
for rest in permutation(arr[:i] + arr[i+1:], n - 1):
result.append([elem] + rest)
return result
print(permutation([0,1,2,3], 2))
# [[0, 1], [0, 2], [0, 3], [1, 0], [1, 2], [1, 3], [2, 0], [2, 1], [2, 3], [3, 0], [3, 1], [3, 2]]• Reference