[순열/조합] itertools 라이브러리를 이용하여 순열/조합 구하기

오늘은 Python의 itertools 라이브러리를 이용하여 순열, 조합을 쉽게 구현하는 방법에 대해 알아보자! 

 

개념

순열 (permutation)

서로 다른 n개에서 r를 선택하여 순서 있게 나열하는 것

• 이를 nPr로 표현한다.
• nPr = n! / (n - r)! (단, r <= n)

 

조합 (combination)

서로 다른 n개에서 순서에 관계없이 서로 다른 r개를 선택하는 것

• 이를 nCr로 표현한다.
• nCr = n! / r!(n - r)! (단, r <= n)

 

순열과 조합 차이

순열과 조합의 차이를 이해하기 위해 서로 다른 과일 4개가 있다고 가정해보자. (🍓, 🍋, 🥝, 🍇)

 

1. 순열 ➡️ 서로 다른 과일 2개를 선택하여 순서대로 나열하는 것이다.

• 이렇게 12가지의 경우가 나온다.

2. 조합 ➡️ 서로 다른 과일 2개를 선택하는 것이다. (선택하는 것으로 끝!)

 

• 조합은 순서가 달라도 구성 과일이 동일하면 같은 경우로 생각하므로 6가지가 나온다.

📌 정리
- 순열은 순서를 꼭 따져주어야 한다.
- 조합은 순서와 관계없이 구성원만 본다.

 

코드

python에서 제공하는 itertools 라이브러리를 사용하면 순열과 조합을 간단하게 구할 수 있다.

itertools 라이브러리

Functions creating iterators for efficient looping
: 효율적인 반복을 위한 iterator(반복자)를 생성하는 함수

• iterator 객체는 값을 차례대로 꺼낼 수 있는 객체를 말한다.
• iterator는 iterable(즉, 반복 가능한) 객체를 생성할 수 있다.

즉, itertools 라이브러리는 python에서 반복되는 형태의 데이터를 처리하기 위한 기능을 제공한다.

 

itertools 라이브러리는 다음과 같이 import 하면 된다.

import itertools

만약 순열과 조합 중 하나만 사용할 경우 다음과 같이 import 하면 더욱 간편하게 사용할 수 있다.

from itertools import permutations

from itertools import combinations

 

순열

permutations(data, r)

• data: 데이터가 담긴 리스트
• r: 그 뒤에는 선택하고 싶은 원소의 개수 (입력하지 않으면 n개가 선택된다.)

from itertools import permutations

data = [1, 2, 3, 4]

for x in permutations(data, 2):
    print(list(x), end=' ')

실행 결과

[1, 2] [1, 3] [1, 4] [2, 1] [2, 3] [2, 4] [3, 1] [3, 2] [3, 4] [4, 1] [4, 2] [4, 3]

 

조합 ( combinations )

combinations(data, r)

• data: 데이터가 담긴 리스트
• r: 그 뒤에는 선택하고 싶은 원소의 개수 (입력하지 않으면 n개가 선택된다. (즉, 1개의 결과만 나온다.))

from itertools import combinations

data = [1, 2, 3, 4]

for x in combinations(data, 2):
    print(list(x), end=' ')

실행 결과

[1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] 

위에서 본 과일 예제와 동일한 결과가 나온다!

 

Reference

https://wikidocs.net/16068
https://widekey6.tistory.com/105
https://docs.python.org/ko/3/library/itertools.html