[Python] 파이썬 순열, 조합, 중복순열, 중복조합

파이썬 순열, 조합, 중복순열, 중복조합

순열, 조합, 중복순열, 중복조합과 파이썬에서 이를 어떻게 계산하는지 알아봅니다.

순열과 조합, 그리고 중복

---

먼저 네 가지의 경우의 수를 표로 정리하여 보도록 합니다. 표현

	순서	중복	예시	배열 방법
순열	O	X	~3~P~2~	(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)
중복 순열	O	O	~3~𝜫~2~	(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)
조합	X	X	~3~C~2~	(1,2),(1,3),(2,3)
중복조합	X	O	~3~H~2~	(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)

• 조합은 원소의 순서를 고려하지 않습니다.
• 순열은 원소의 순서를 고려합니다.
• 중복은 원소의 중복을 허용합니다.

1. 순열

---

파이썬에서 순열은 permutations을 사용하여 구현할 수 있습니다.

from itertools import permutations as P

N, M = map(int, input().split())
for p in P(range(1,N+1),M): print(*p)

in:
3 2
  
out: 
1 2
1 3
2 1
2 3
3 1
3 2

permutations의 파라미터로는 순열을 생성할 iterable 객체와 순열을 구성할 원소의 개수를 전달합니다.

2. 조합

---

파이썬에서 조합은 combinations을 사용하여 구현할 수 있습니다.

from itertools import combinations as C

N, M = map(int, input().split())
for c in C(range(1,N+1),M): print(*c)

in:
3 2
  
out: 
1 2
1 3
2 3

combinations의 파라미터로는 마찬가지로 조합을 생성할 iterable 객체와 조합을 구성할 원소의 개수를 전달합니다.

3. 중복 순열

---

파이썬에서 중복 순열은 product를 사용하여 구현할 수 있습니다.

from itertools import product as PI

N, M = map(int, input().split())
for pi in PI(range(1,N+1),repeat=M): print(*pi)
# for pi in PI(*([range(1,N+1)]*M)): print(*pi)

in:
3 2
  
out: 
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

permutations, combinations와는 조금 다르게 product의 파라미터로는 중복 순열의 원소를 뽑아올 iterable 객체들을 전달합니다.

예를 들어 product의 인자로 product([1,2],[3,4],[5,6,7])을 전달하면 각각의 리스트에서 원소 하나씩을 선택해 생성할 수 있는 중복순열을 반환합니다.

만약 각 리스트가 동일하다면, 즉 하나의 리스트에서 중복 순열을 생성하고 싶다면 repeat 파라미터를 지정하여 뽑을 원소의 개수를 지정할 수 있습니다.

4. 중복 조합

---

파이썬에서 중복 조합은 combinations_with_replacement를 사용하여 구현할 수 있습니다.

from itertools import combinations_with_replacement as H

N, M = map(int, input().split())
for h in H(range(1,N+1),M): print(*h)

in:
3 2
  
out: 
1 1
1 2
1 3
2 2
2 3
3 3

combinations_with_replacement는 permutations, combinations와 마찬가지로 파라미터로 중복 조합을 생성할 iterable 객체와 중복 조합을 구성할 원소의 개수를 전달합니다.

정리

---

• 경우의 수를 생성해내는 데에는 순열, 조합, 중복 순열, 중복 조합의 4 가지 방법이 있습니다.
  • 순열은 permutations를 사용합니다.
  • 조합은 combinations를 사용합니다.
  • 중복 순열은 product를 사용합니다.
  • 중복 조합은 combinaitons_with_replacement를 사용합니다.