[알고리즘] 순열과 조합

개요

순열과 조합은 서로 다른 n개의 원소에서 r개를 선택하는 경우의 수를 다룬다. 이 둘의 차이점은, 순열은 원소를 뽑는 순서가 다르면 다른 케이스로 구분하지만, 조합은 뽑는 순서가 다르더라도 원소가 같으면 같은 케이스로 구분한다.

예를 들어 원소 A, B, C에서 두 개를 선택하는 상황이 있다고 가정하자. 순열에서는 [A, B]와 [B, A]는 다른 케이스로 처리되지만 조합에서는 [A, B]와 [B, A]를 같은 케이스로 처리한다.

순열과 조합은 아래와 같은 수식으로 구할 수 있다.

• 순열을 구하는 수식: nPr = n! / (n - r)!
• 조합을 구하는 수식: nCr = n! / ((n - r)! * r!)

파이썬에서 순열과 조합을 구하는 방법

파이썬 라이브러리 itertools를 이용하여 순열과 조합을 구할 수 있다.

from itertools import combinations, permutations

arr = ["A", "B", "C"]
nPr = permutations(arr, 2) # 집합 A, B, C에서 두 개를 고르는 순열
nCr = combinations(arr, 2) # 집합 A, B, C에서 두 개를 고르는 조합

print(list(nPr)) # [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
print(list(nCr)) # [('A', 'B'), ('A', 'C'), ('B', 'C')]