[Probability]순열(permutation)

순열(Permutaion)

경우의 수

주사위 2개를 시행할 경우 발생되는 모든 경우는 다음과 같습니다.

event=[]
for i in range(1, 7):
for j in range(1, 7):
event.append((i, j))

print(event, end="")
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

$\begin{array}{cccccc}\text{(1, 1)}& \text{(1, 2)}& \text{(1, 3)}& \text{(1, 4)}& \text{(1, 5)}& \text{(1, 6)}\\ \text{(2, 1)}& \text{(2, 2)}& \text{(2, 3)}& \text{(2, 4)}& \text{(2, 5)}& \text{(2, 6)}\\ \text{(3, 1)}& \text{(3, 2)}& \text{(3, 3)}& \text{(3, 4)}& \text{(3, 5)}& \text{(3, 6)}\\ \text{(4, 1)}& \text{(4, 2)}& \text{(4, 3)}& \text{(4, 4)}& \text{(4, 5)}& \text{(4, 6)}\\ \text{(5, 1)}& \text{(5, 2)}& \text{(5, 3)}& \text{(5, 4)}& \text{(5, 5)}& \text{(5, 6)}\\ \text{(6, 1)}& \text{(6, 2)}& \text{(6, 3)}& \text{(6, 4)}& \text{(6, 5)}& \text{(6, 6)}\end{array}$

위 결과는 다음과 같이 정리할 수 있습니다. 첫번째 주사위의 각 점의 수에서 두번째 주사위의 1~6의 점들을 모든 점들을 갖는 경우들을 나타냅니다. 그러므로 6 × 6으로 계산할 수 있습니다. 이것은 다음과 같이 일반화할 수 있습니다.

두 실험을 실행하는 경우 실험 1와 2 에서 발생할 수 있는 모든 경우가 m과 n이라면 두 실험을 함께 시행할 경우 발생하는 모든 경우의 수는 m × n 으로 계산합니다.

예) 3개의 파란공과 10개의 빨간공을 쌍으로 연결할 경우 발생하는 경우는 다음과 같습니다.

blue=['b'+str(i) for i in range(1, 4)]
red=['r'+str(j) for j in range(1, 11)]


blue
['b1', 'b2', 'b3']
red
['r1', 'r2', 'r3', 'r4', 'r5', 'r6', 'r7', 'r8', 'r9', 'r10']
re=[]
for i in blue:

print( )
for j in red:
print((i, j), end="")
re.append((i, j))
('b1', 'r1')('b1', 'r2')('b1', 'r3')('b1', 'r4')('b1', 'r5')('b1', 'r6')('b1', 'r7')('b1', 'r8')('b1', 'r9')('b1', 'r10')
('b2', 'r1')('b2', 'r2')('b2', 'r3')('b2', 'r4')('b2', 'r5')('b2', 'r6')('b2', 'r7')('b2', 'r8')('b2', 'r9')('b2', 'r10')
('b3', 'r1')('b3', 'r2')('b3', 'r3')('b3', 'r4')('b3', 'r5')('b3', 'r6')('b3', 'r7')('b3', 'r8')('b3', 'r9')('b3', 'r10')

allCase=len(re)
allCase
30

allCase2=3*10 #위 공식을 적용(n × m)
allCase2
30

예) 1학년 3명, 2학년 5명, 3학년의 2명으로 구성된 클래스에서 3명으로 구성된 소그룹을 만들수 있는 경우의 수를 생각해 봅니다.

f=["f"+ str(i) for i in range(1, 4)]
s=["s"+ str(i) for i in range(1, 6)]
j=["j"+ str(i) for i in range(1, 3)]
f
['f1', 'f2', 'f3']

s
['s1', 's2', 's3', 's4', 's5']

j
['j1', 'j2']

re=[]
for l in f:
print()
for m in s:
print()
for n in j:
print((l, m, n), end="")
re.append((i, s, j))
('f1', 's1', 'j1')('f1', 's1', 'j2')
('f1', 's2', 'j1')('f1', 's2', 'j2')
('f1', 's3', 'j1')('f1', 's3', 'j2')
('f1', 's4', 'j1')('f1', 's4', 'j2')
('f1', 's5', 'j1')('f1', 's5', 'j2')


('f2', 's1', 'j1')('f2', 's1', 'j2')
('f2', 's2', 'j1')('f2', 's2', 'j2')
('f2', 's3', 'j1')('f2', 's3', 'j2')
('f2', 's4', 'j1')('f2', 's4', 'j2')
('f2', 's5', 'j1')('f2', 's5', 'j2')


('f3', 's1', 'j1')('f3', 's1', 'j2')
('f3', 's2', 'j1')('f3', 's2', 'j2')
('f3', 's3', 'j1')('f3', 's3', 'j2')
('f3', 's4', 'j1')('f3', 's4', 'j2')
('f3', 's5', 'j1')('f3', 's5', 'j2')

AllCase=len(re)
AllCase
30

위 예의 총 경우의 수는 30으로 위 정의를 확장하여 다음과 같이 계산할 수 있습니다.

각 시험은 n₁, n₂, ..., n_r로 구성된 r개의 실험들에서 총 경우의 수는 다음과 같이 계산됩니다.
n₁ × n₂ × ... × n_r

예) 비밀번호를 8개를 생성하고자 합니다. 처음 4개는 알파벳 문자이고 나머지 4개는 숫자로 구성하여야 하는 경우 다른 번호를 생성할 모든 경우의 수는?

26*26*26*26*10*10*10*10
4569760000

위의 예에서 반복이 허가되지 않은 경우?

26*(26-1)*(26-2)*(26-3)*10*(10-1)*(10-2)*(10-3)
1808352000

Permutation

문자 a, b, c를 순서있게 배열하는 경우는 다음과 같습니다.

$\begin{array}{cc}\text{abc}& \text{acb}\\ \text{bac}& \text{bca}\\ \text{cab}& \text{cba}\end{array}$

총 6개의 경우의 수가 존재합니다. 이와같이 샘플들을 순서를 고려하여 반복 없이 정렬하는 배열방법을 permutation이라고 합니다. permutatioin의 경우의 수는 다음과 같이 계산할 수 있습니다.

3·2·1 = 6

위의 식을 일반화하면 n개의 샘플들을 순서있게 배열하는 총 경우의 수는 다음과 같습니다.
n·(n-1)·(n-2)·…·2·1 = n!
factorial(!)은 python의 math 모듈 함수 factorial()을 사용하여 계산할 수 있습니다.

permutation은 python의 itertools 모듈의 함수를 사용하여 계산할 수 있습니다.

itertools.permutations(x, n): 객체 x에서 n개를 선택하여 정렬시킨 결과를 반환

import itertools
list(itertools.permutations(da, 3))
[('a', 'b', 'c'),
('a', 'c', 'b'),
('b', 'a', 'c'),
('b', 'c', 'a'),
('c', 'a', 'b'),
('c', 'b', 'a')]

야구 팀 타자들의 순서를 정하는 방법 역시 순열과 같습니다.

import math
math.factorial(9)

362880

x=list(range(1, 10))
list(itertools.permutations(x, 9))
[(1, 2, 3, 4, 5, 6, 7, 8, 9),
(1, 2, 3, 4, 5, 6, 7, 9, 8),
… ]

10권 책들을 정리하려고 합니다. 3권은 소설, 4권을 전공서적, 3권은 만화책입니다.
정리할 수 있는 총 경우의 수는 10!이 됩니다. 그러면 각 분야별로 정리하는 방법의 수는 어떻게 계산될까요?
소설: 3!, 전공서적: 4!, 만화: 3! 그리고 각 분야를 나열하는 방법:3!을 고려합니다.

x=[3,4,3,3]
re=1
for i in x:
re *= math.factorial(i)
re
5184

위의 예에서 각 분야의 책들이 같다면 분야내에서 순서는 의미가 없을 것입니다. 이 경우 배열 방법은 어떻게 계산할까요? 이문제를 고려하기전에 간단한 예인 a,a,b의 정렬을 생각해 봅니다. 먼저 a를 a1과 a2로 구분하여 정렬하여 보면 다음과 같이 6가지 방법으로 정렬할 수 있습니다.

x=['a1', 'a2', 'b']
list(enumerate(itertools.permutations(x, 3)))
[(0, ('a1', 'a2', 'b')),
(1, ('a1', 'b', 'a2')),
(2, ('a2', 'a1', 'b')),
(3, ('a2', 'b', 'a1')),
(4, ('b', 'a1', 'a2')),
(5, ('b', 'a2', 'a1'))]

위 결과에서 a1=a2라면 b의 위치에 따라 다음과 같이 고려할 수 있습니다.

• ('a1', 'a2', 'b') = ('a2', 'a1', 'b')
• ('a1', 'b', 'a2') = ('a2', 'b', 'a1'))
• ('b', 'a1', 'a2') = ('b', 'a2', 'a1')

결과적으로 다음과 같이 계산할 수 있습니다.

$\frac{\text{3!}}{\text{2!}}$

이러한 계산과정은 다음과 같이 일반화 할 수 있습니다.

전체 객체의 수 n 개가 다음과 같이 구성되어 있는 경우
n=n₁+n₂+…+n_r-1+n_r
위 객체를 정렬하는 총 경우의 수는 다음과 같이 계산할 수 있습니다.
$\frac{\text{n!}}{n_1!n_2!\dots n_{\text{(r-1)}}!n_r!}$

위 식을 적용하여 서적 배열 방법의 경우의 수는 다음과 같습니다.

p=[3,4,3]
re1=1
for i in p:
re1 *= math.factorial(i)
re1
864

math.factorial(10)/re1
4200.0