✏️ 순열(Permutation)
👉🏻 순열은 순서를 고려하여 뽑는 경우의 수다.
nPr : 서로 다른 n개에서 r개를 택하여 일렬로 나열하는 경우의 수.
nPr = n!/(n-r)! = nx(n-1)x(n-2)x...x(n-r+1)
예시) 1,2,3,4,5가 적혀 있는 숫자 카드가 있다. 이를 이용해 세 자리 수를 만들 수 있는 방법은?
백의 자리에 올 수 있는 경우의 수: 5
십의 자리에 올 수 있는 경우의 수: 4
일의 자리에 올 수 있는 경우의 수: 3
백의 자리에 1이 올 때, 십의 자리에 올 수 있는 경우의 수는 2,3,4,5로 4가지이다. 이는 백의 자리에 2,3,4,5가 올 때도 동일하다. 따라서 이는 5x4x3으로 곱의 법칙이 된다.
결론적으로, 서로 다른 숫자 5개 중에서 3개를 택하여 일렬로 배열한 경우의 수로
5P3 = 5x4x3 = 60
✨ 다음은 itertools 라이브러리에서 permutations함수를 활용한 순열 구현이다.
from itertools import permutations
sets = [1,2,3]
data = itertools.permutation(sets, 2)
for i in data:
print(i)
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)
✏️ 조합(combination)
👉🏻 조합은 순서를 생각하지 않고 뽑는 경우의 수다.
nCr : 서로 다른 n개에서 순서를 생각하지 않고 r개를 택하는 경우의 수.
nCr = n!/(n-r)!r! = nPr/r! = {n(n-1)(n-2)...(n-r+1)}/r!
예시) A,B,C,D,E 5명의 후보가 있다. 이 중 2명의 대표를 뽑는 방법은?
(A,B),(A,C),(A,D),(A,E)
(B,C),(B,D),(B,E)
(C,D),(C,E)
(D,E)
조합은 순서를 생각하지 않으므로 (A,B)와 (B,A)를 같은 것으로 본다.
즉, 순열은 5P2 = 5x4 = 20이지만 조합은 (5x5)/2 = 10 이다.
5C2 = 5P2/(2x1) = (5x4)/(2x1) = 10
✨ 다음은 itertools 라이브러리에서 combinations함수를 활용한 조합 구현이다.
from itertools import combinations
sets = ['A', 'B', 'C']
data = itertools.combinations(sets, 2)
for i in data:
print(i)
(A, B)
(A, C)
(B, C)
✏️ 중복순열(Permutation with repetition)
👉🏻 중복순열은 순열과는 다르게 같은 숫자를 중복하여 사용할 수 있다.
nπr : 중복 가능한 n개에서 r개를 택하여 일렬로 나열하는 경우의 수.
nπr = n^r
예시) 1,2,3,4,5가 적혀 있는 숫자 카드가 있다. 이를 중복을 허용해 세 자리 수를 만들 수 있는 방법은?
백의 자리에 올 수 있는 경우의 수: 5
십의 자리에 올 수 있는 경우의 수: 5
일의 자리에 올 수 있는 경우의 수: 5
백의 자리에 1이 올 때, 십의 자리에 올 수 있는 경우의 수는 1,2,3,4,5로 5가지이다. 이는 백의 자리에 2,3,4,5가 올 때도 동일하다. 따라서 이는 5x5x5로 5^3이 된다.
결론적으로, 서로 다른 숫자 5개 중에서 중복을 허용해 3개를 택하여 일렬로 배열한 경우의 수로
5π3 = 5x5x5 = 125
✨ 다음은 itertools 라이브러리에서 product함수를 활용한 중복순열 구현이다.
from itertools import product
sets = [1,2,3]
#2개를 뽑아 일렬로 나열하는 경우의 수(단, 중복 허용)
data = itertools.product(sets, repeat = 2)
for i in data:
print(i)
(1, 1)
(1, 2)
(1, 3)
(2, 1)
(2, 2)
(2, 3)
(3, 1)
(3, 2)
(3, 3)
✏️ 중복조합(Combination with repetition)
👉🏻 중복조합은 조합과는 다르게 같은 숫자를 중복하여 사용할 수 있다.
nHr : 중복 가능한 n개에서 순서를 생각하지 않고 r개를 택하는 경우의 수
<예시) A,B,C,D,E 5명의 후보가 있다. 이를 중복을 허용해 2명의 대표를 뽑는 방법은?
(A, A), (A, B), (A, C), (A, D), (A, E)
(B, B), (B, C), (B, D), (B, E)
(C, C), (C, D), (C, E)
(D, D), (D, E)
(E, E)
조합은 순서를 생각하지 않으므로 (A,B)와 (B,A)를 같은 것으로 본다. 이 중 중복이 가능하니 (A,A)로 한 명이 대표직 2개를 겸할 수 있다.
6C2 = 6P2/r! = (6x5)/(2x1) = 15
✨ 다음은 itertools 라이브러리에서 combinations_with_replacement 함수를 활용한 중복조합 구현이다.
from itertools import combinationswith_replacement
sets = ['A', 'B', 'C']
data = itertools.combinations_with_replacement(sets, 2)
for i in data:
print(i)
#print_
(A, A)
(A, B)
(A, C)
(B, B)
(B, C)
(C, C)
