[알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬)

순열과 조합

• 경우의수
  • 한 번의 시행에서 일어날 수 있는 사건의 가지 수
  • 재귀 함수, 반복문을 이용해서 직접 구현 가능하지만 실제 코딩테스트에서 직접 구현하기는 매우 번거롭다

순열 (Permutation)

• 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것
• $nPr = n! / (n-r)!$
• 코딩테스트에서는 경우의 수 값만 출력하는 것이 아니라 모든 경우(사건)를 다 출력하도록 요구
• 파이썬 itertools 라이브러리를 이용한다.

import itertools

data = [1, 2, 3]

for x in itertools.permutations(data,2):
        print(list(x), end= '')
# [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2]

조합 (Combination)

• 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것
• $nCr = n! / r! * (n-r)!$

import itertools

data = [1, 2, 3]

for x in itertools.combinations(data, 2):
        print(list(x), end= ' ')
# [1, 2] [1, 3] [2, 3]