이 글에서는 파이썬(Python) 프로그래밍 언어를 사용해 주어진 시퀀스의 순열(permutation)과 조합(combination)을 구하는 방법을 알아봅니다.
파이썬이 다른 프로그래밍 언어에 비해 갖는 가장 큰 장점 중 하나는 방대한 표준 라이브러리를 기본으로 제공한다는 점입니다. 별도의 설치 없이 내장 패키지인 itertools만으로도 순열과 조합을 손쉽게 계산할 수 있습니다.
순열과 조합을 구하는 알고리즘
1단계: 필요한 패키지 임포트하기
가장 먼저 필요한 패키지를 임포트합니다. 여기서는 itertools 패키지를 사용하므로 아래와 같이 불러옵니다.
>>> import itertools >>>
2단계: 시퀀스의 모든 순열과 조합 생성하기
다음으로 리스트나 문자열 등 시퀀스를 입력값으로 전달하면, 모든 순열과 조합이 튜플(tuple)의 리스트 형태로 반환됩니다. 이때 두 번째 인자로 길이를 지정하면 원하는 개수만큼의 요소로 이루어진 순열·조합만 추출할 수도 있습니다.
3단계: 결과 출력하기
마지막 단계는 생성된 모든 순열과 조합을 출력하는 것입니다. 반복문(for 루프)을 활용하면 결과를 깔끔하게 확인할 수 있습니다.
순열(Permutation)
순열은 요소들의 순서가 중요할 때 사용합니다. 세 개의 요소를 가진 리스트의 순열을 구해 보겠습니다.
예제 1: 전체 순열 구하기
from itertools import permutations
seq = permutations(['a','b','c'])
for p in list(seq):
print(p)실행 결과
('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')3개의 요소로 만들 수 있는 모든 경우의 수, 즉 3! = 6가지 순열이 출력되었습니다.
예제 2: 길이를 지정한 순열 구하기
두 번째 인자에 숫자를 넣으면 해당 길이의 순열만 얻을 수 있습니다. 아래 예제는 'python'이라는 6개 문자에서 2개를 뽑아 나열하는 순열입니다.
from itertools import permutations
seq = permutations(['p', 'y', 't', 'h', 'o', 'n'], 2)
for p in list(seq):
print(p)실행 결과
('p', 'y')
('p', 't')
('p', 'h')
('p', 'o')
('p', 'n')
('y', 'p')
('y', 't')
('y', 'h')
('y', 'o')
('y', 'n')
('t', 'p')
('t', 'y')
('t', 'h')
('t', 'o')
('t', 'n')
('h', 'p')
('h', 'y')
('h', 't')
('h', 'o')
('h', 'n')
('o', 'p')
('o', 'y')
('o', 't')
('o', 'h')
('o', 'n')
('n', 'p')
('n', 'y')
('n', 't')
('n', 'h')
('n', 'o')순서가 다르면 서로 다른 것으로 간주되므로 ('p', 'y')와 ('y', 'p')가 모두 포함됩니다. 총 6P2 = 30가지입니다.
조합(Combination)
조합은 요소들의 순서가 중요하지 않을 때 사용합니다. 파이썬으로 조합을 구하는 방법을 살펴보겠습니다.
예제 1: 길이를 지정한 조합 구하기
# itertools 패키지 임포트
from itertools import combinations
# 특정 길이의 모든 조합 구하기
combi = combinations(['p', 'y', 't', 'h', 'o', 'n'], 5)
# 조합 리스트 출력
for c in list(combi):
print(c)실행 결과
('p', 'y', 't', 'h', 'o')
('p', 'y', 't', 'h', 'n')
('p', 'y', 't', 'o', 'n')
('p', 'y', 'h', 'o', 'n')
('p', 't', 'h', 'o', 'n')
('y', 't', 'h', 'o', 'n')순서를 고려하지 않기 때문에 6개 중 5개를 뽑는 조합은 6C5 = 6가지뿐입니다. 순열과 달리 같은 요소 집합은 한 번만 등장합니다.
예제 2: 중복을 허용하는 조합 구하기
combinations_with_replacement 함수를 사용하면 같은 요소를 중복해서 선택할 수 있는 조합을 구할 수 있습니다.
# itertools 패키지 임포트
from itertools import combinations_with_replacement
# 특정 길이를 지정해 모든 조합 구하기
combi = combinations_with_replacement(['p', 'y', 't', 'h', 'o', 'n'], 2)
# 조합 리스트 출력
for c in list(combi):
print(c)실행 결과
('p', 'p')
('p', 'y')
('p', 't')
('p', 'h')
('p', 'o')
('p', 'n')
('y', 'y')
('y', 't')
('y', 'h')
('y', 'o')
('y', 'n')
('t', 't')
('t', 'h')
('t', 'o')
('t', 'n')
('h', 'h')
('h', 'o')
('h', 'n')
('o', 'o')
('o', 'n')
('n', 'n')('p', 'p')처럼 동일한 요소가 두 번 선택된 결과도 포함되며, 순서는 항상 입력 순서대로 유지되므로 ('p', 'y')와 ('y', 'p')처럼 중복된 쌍은 나오지 않습니다.
정리
파이썬의 itertools 패키지를 활용하면 복잡한 수학 공식을 직접 구현하지 않고도 순열과 조합을 몇 줄의 코드로 해결할 수 있습니다.
- permutations(): 순서가 중요한 순열 생성
- combinations(): 순서가 없는 조합 생성
- combinations_with_replacement(): 중복 선택이 가능한 조합 생성
알고리즘 문제 풀이나 데이터 분석 등 다양한 상황에서 유용하게 활용해 보시기 바랍니다.