조합과 순열 구현해보기 - Python

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

https://cotak.tistory.com/70