[알고리즘] 조합, 순열 알고리즘 (파이썬)

알고리즘 문제, 코딩 테스트를 하면 종종 나오는 조합, 순열을 구하는 방법을 정리해보도록 하겠습니다.

 

순열

순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음)

위와 같은 공식으로 순열의 개수를 구할 수 있습니다.

 

순열을 구하는 코드는 재귀함수를 이용할 수 있습니다.

 

 

def perm(result, arr, depth, n, k):
    if depth == k:
        result.append(arr.copy()[:k])
        return

    for i in range(depth, n):
        arr[i], arr[depth] = arr[depth], arr[i]
        perm(result, arr, depth + 1, n, k)
        arr[i], arr[depth] = arr[depth], arr[i]

    return result


print(perm([], [1, 2, 3, 4], 0, 4, 2))

# 결과
# [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 2], [3, 1], [3, 4], [4, 2], [4, 3], [4, 1]]

 

result는 순열을 담을 배열입니다. 초기 값은 빈 배열입니다.

arr은 계속적으로 바뀌는 순열의 현재 값입니다.

depth는 현재 순열의 깊이? 입니다. 몇번째 자리까지 순열을 구했는지 표현합니다.

n은 전체 길이 입니다. arr이 계속 변하기 때문에 따로 길이를 넘겨줍니다.

k는 몇가지 요소로 순열을 구성할 것인가 입니다.

 

 

그렇다면 위와 같이 재귀함수가 실행됩니다 (depth가 4일 경우)

depth가 내려갈 수록 앞자리들이 고정되며 뒷자리들만 변하게 됩니다.

 

 

 

조합

조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음)

 

위와 같은 공식으로 순열의 개수를 구할 수 있습니다.

 

조합을 구하는 코드는 다른 방법을 사용할 수도 있지만 순열을 구하는 코드에서 중복된 배열이 있는지만 확인하면 간단히 구할 수 있습니다.

 

간단한 활용이기에 따로 코드를 작성하지 않겠습니다.

 

---

파이썬 모듈

위와 같이 재귀함수를 이용할 수도있지만 파이썬의 모듈을 활용할 수 있습니다.

from itertools import permutations
from itertools import combinations

items = [1, 2, 3, 4]

print(list(permutations(items, 2)))
print(list(combinations(items, 2)))

# 결과
# [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

 

itertools를 이용하면 위와 같이 쉽게 결과를 얻을 수 있습니다.

---

참고 자료

coding-factory.tistory.com/606