[파이썬/Python] 순열과 조합 (Permutation and Combination)

순열과 조합

순열 (Permutation)

순열이란 서로 다른 n개에서 r개를 선택할 때 순서를 고려하여 선택한 경우의 수를 나열하는 방법이다. 보통 Permutation의 첫 글자 P를 따서 nPr로 표현하며 계산식은 아래와 같이 쓸 수 있다. 0 ≦ r ≦ n

• nPr = n x (n-1) x (n-2) x (n-3) x …… x (n-r+1) ※ n부터 (n-r+1)까지 곱해지는 수는 총 r개
• nPr = n! / (n-r)!

가령, 알파벳이 써져 있는 카드 4개가 있다고 해보자. 각 카드에는 A, B, C, D가 써져 있는데 이 중에서 순서를 고려하여 2장을 뽑고 싶다고 하자. 공식에 따르면 4P2 = 4 x 3 = 12 혹은 4P2 = 4! / (4-2)! = 4 x 3 x 2 x 1 / 2 x 1 = 4 x 3 = 12 이므로 총 12개의 경우의 수가 나올 것이라 생각할 수 있다. 실제로 2장을 뽑은 결과를 나열하면 다음과 같다.

 

AB, AC, AD

BA, BC, BD

CA, CB, CD

DA, DB, DC

 

여기서 순서를 고려한다는 것은, AB와 BA를 서로 다른 것이라고 여기는 것을 의미한다.

 

조합 (Combination)

순열이란 서로 다른 n개에서 r개를 선택할 때 순서를 고려하지 않고 선택한 경우의 수를 나열하는 방법이다. 보통 Combination의 첫 글자 C를 따서 nCr로 표현하며 계산식은 아래와 같이 쓸 수 있다.

• nCr = n x (n-1) x (n-2) x …… x (n-r+1) / r x (r-1) x (r-2) x …… x 2 x 1
• nCr = n! / r!(n-r)!

앞서 순열에서 들었던 카드 예시를 조합에 대입해보자. 이번에는 순서를 고려하지 않고 경우의 수를 세어 볼 것인데, 공식에 따르면 4C2 = 4 x 3 / 2 x 1 = 6 혹은 4C2 = 4! / 2!(4-2)! = 4 x 3 x 2 x 1 / 2 x 1 x 2 x 1 = 6 이므로 총 6개의 경우의 수가 나올 것이라 생각할 수 있다.

 

AB, AC, AD

BA, BC, BD

CA, CB, CD

DA, DB, DC

 

순열과 조합의 차이를 한 눈에 알아볼 수 있게 순열의 결과물에서 제외된 카드 세트를 회색으로 표시하였다. 이렇듯 조합에서는 순열과 달리 AB와 BA를 서로 같은 것이라고 여기는 특징이 있다.

 

순열과 조합을 위한 Python 모듈, itertools

갑자기 고등학교 수학 시간에 배우는 내용을 왜 읊었냐면, Python에는 순열과 조합을 손쉽게 만들어주는 모듈 itertools가 있다. 백문이 불여일타라고, 말할 것도 없이 일단 코드를 쳐보자.

from itertools import permutations, combinations

arr = ['A', 'B', 'C', 'D']

permute = list(permutations(arr,2))
combi = list(combinations(arr,2))

print(permute)
# [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'A'), ('B', 'C'), ('B', 'D'), 
#  ('C', 'A'), ('C', 'B'), ('C', 'D'), ('D', 'A'), ('D', 'B'), ('D', 'C')]

print(combi)
# [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

먼저 순열과 조합을 만드는 메서드를 사용하기 위해 itertools 모듈에서 permutations와 combinations를 import해준다.

 

이후 순열 혹은 조합을 만들고 싶은 요소 n개가 들어있는 리스트 'arr'와 몇 개를 뽑을 것인지 'r'을 선택하고, permutations 메서드 혹은 combinations 메서드의 인자값으로 그 두 개를 집어 넣는다. 여기서 첫번째 인자값으로는 꼭 리스트여야 하고 두 번째 인자값으로는 꼭 int형이 들어와야 하냐 궁금해할 수 있는데, 두 번째 인자값은 꼭 int형이 들어와야 되지만 첫 번째 인자값은 꼭 그렇지만은 않다. 리스트 뿐만 아니고 튜플, 문자열, 집합, 딕셔너리 모두 인자로 사용할 수 있다. 하지만 집합은 자료형 특성상 조합과 순열을 만들기에는 적합하지 않기 때문에 쓰는 것을 많이 못 봤다. 딕셔너리 또한 key만을 이용하여 조합과 순열을 만들어내는데, 딱히 딕셔너리 형태에서 이런 짓을 할 일은 별로 없을 것 같다. 그러면 집합과 딕셔너리 자료형은 딱히 itertools를 쓸 일이 없어 보인다는 결론이 나온다.

 

그렇다. 딕셔너리와 집합 자료형을 빼고 나면 리스트, 튜플, 문자열 자료형만이 남는데 이것들은 대표적인 반복 가능(iterable)한 자료형이라는 것을 알 수 있다! itertools는 실제로 자료형 내부의 member 하나씩을 순회하며 효과적인 작업 처리를 하는 메서드들을 포함시킨 모듈이다. 그래서 itertools 관련 공식문서를 보면, 대부분의 메서드에 대한 설명에서 인자값으로 iterable한 객체들로 넣으라고 써져 있다.

 

인자값에 관하여 궁금하다면 혼자 IDLE에 쳐보며 어떤 식으로 조합과 순열이 만들어지는지 느껴보는 것을 권장하며, 보다 고급지고 복잡한 사용 예시, 정석적인 설명들을 보고 싶다면 공식문서를 확인하자.

 

또한 permutations 메서드 혹은 combinations 메서드를 이용한 후에는 그것을 list( ) 메서드나 tuple( ) 메서드로 캐스팅해주어야 한다. 캐스팅해주지 않으면 출력할 때 'itertools.permutations object at 0x036B95A0'와 같이 0x036B95A0라는 주소에 있는 객체라고만 뜬다. 우리가 원하는 값을 보고 싶다면 꼭! 리스트나 튜플로 형태를 변환시켜줘야 한다.

 

그렇게 캐스팅까지 마친 순열 혹은 조합을 출력해보면 각 카드 세트들은 하나의 튜플 안에 감싸져서 하나의 요소로 들어가게 된다.

 

중복 순열

보너스로 순열 중에서도 중복 순열을 만드는 메서드 product( )에 대해서 짧게 설명하며 글을 마무리하겠다.

 

순열에서는 한 번 고른 것은 다시 고를 수 없는 것이 원칙이다. 그러나 특별히 중복을 허용하여 n 개 중 r 개를 순서 있게 나열하는 것을 중복순열이라 하며 기호로는 nΠr로 나타낸다. 이때 중복 순열 nΠr 은 n^r개의 경우의 수를 의미한다.

 

또 다시 앞서 예시로 들었던 카드를 써보자. 중복 순열로 2장을 선택할 때 다음과 같이 나열될 수 있다.

 

AA, AB, AC, AD

BA, BB, BC, BD

CA, CB, CC, CD

DA, DB, DC, DD

 

위에서 볼 수 있듯이 AA나 BB, CC, DD처럼 중복을 허용하여 순열을 만들어내게 된다. 그러면 중복순열을 한 번 구현해보자.

from itertools import product

arr = ['A', 'B', 'C', 'D']
s = 'ABCD'

result_1 = list(product(arr, repeat=2))
result_2 = list(product(s, repeat=2))

print(result_1)
# [('A', 'A'), ('A', 'B'), ('A', 'C'), ('A', 'D'), 
#  ('B', 'A'), ('B', 'B'), ('B', 'C'), ('B', 'D'), 
#  ('C', 'A'), ('C', 'B'), ('C', 'C'), ('C', 'D'), 
#  ('D', 'A'), ('D', 'B'), ('D', 'C'), ('D', 'D')]

print(result_2)
# [('A', 'A'), ('A', 'B'), ('A', 'C'), ('A', 'D'), 
#  ('B', 'A'), ('B', 'B'), ('B', 'C'), ('B', 'D'), 
#  ('C', 'A'), ('C', 'B'), ('C', 'C'), ('C', 'D'), 
#  ('D', 'A'), ('D', 'B'), ('D', 'C'), ('D', 'D')]

앞서 설명했듯이 iterable한 객체라면 itertools 모듈 내부의 메서드의 인자값으로 들어갈 수 있다. 그래서 비교를 하기 위해 arr와 s 두 개를 만들어서 보여주었는데, 두 개의 결과값이 동일한 것을 알 수 있다.

 

근데 만약 하나의 요소가 ('A', 'A') 와 같은 형태가 아니고, 'AA'와 같은 요소로 갖고 싶다면 어떻게 할까? 다음과 같이 살짝만 바꿔주면 된다.

from itertools import product

arr = ['A', 'B', 'C', 'D']
s = 'ABCD'

result_1 = list(product(arr, repeat=2))
result_1 = [''.join(elem) for elem in result_1]

result_2 = list(product(s, repeat=2))
result_2 = [''.join(elem) for elem in result_2]

print(result_1)
# ['AA', 'AB', 'AC', 'AD', 'BA', 'BB', 'BC', 'BD', 
#  'CA', 'CB', 'CC', 'CD', 'DA', 'DB', 'DC', 'DD']

print(result_2)
# ['AA', 'AB', 'AC', 'AD', 'BA', 'BB', 'BC', 'BD', 
#  'CA', 'CB', 'CC', 'CD', 'DA', 'DB', 'DC', 'DD']

이렇게 되면 튜플로 감싸져있던 것들이 문자열로 바뀌어 비교적 이전 코드보다는 더 깔끔한 형태로 알아볼 수 있고 활용도도 더 높아 보인다.

 

정말 아쉬운 점은, 시간복잡도가 상당하여 필요로 하는 조합 혹은 순열의 개수가 약간만 많아져도 알고리즘 테스트에서 활용하기는 쉽지 않다는 것이다.

 

 

Source : 

1. 네이버 지식백과, <순열>

2. 네이버 지식백과, <조합>

3. 네이버 지식백과, <중복순열>