[data analysis] 순열과 조합 (Permutation & Combination)

순열과 조합 (Permutation & Combination)

확률 계산은 표본공간을 기반으로 이루어지지만 많은 경우 표본공간을 계산하는 것은 매우 번거로운 작업 일 수 있습니다. 순열과 조합의 개념은 이 번거로운 부분을 상당히 감소시킵니다. 예를 들어 주사위 2개를 시행의 결과로 생성되는 표본공간은 식 1과 같습니다.

$\begin{align}1:\begin{bmatrix}1\\2\\\vdots\\6\end{bmatrix}&\Rightarrow \begin{bmatrix} (1,1)\\(1,2)\\\vdots\\(1, 6)\end{bmatrix} \\ 2:\begin{bmatrix}1\\2\\\vdots\\6\end{bmatrix}&\Rightarrow \begin{bmatrix} (2,1)\\(2,2)\\\vdots\\(2, 6)\end{bmatrix}\\&\vdots \end{align}$

(식 1)

import itertools
S=list(itertools.product(range(1,7), repeat=2));S

[(1, 1),
(1, 2),
(1, 3),
  ⋮
(6, 6)]

len(S)

36

두 개의 주사위를 던지는 실험에서 주사위 각각의 시행이 서로 영향을 미치지 않습니다. 이러한 시행을 독립시행 또는 상호 배타적 시행이라합니다. 이 경우 생성될 수 있는 모든 경우의 수는 1번 주사위에서 6 가지, 2번 주사위에서 6가지로 총 6 · 6 = 36 가지가 됩니다. 이와 같이 독립사건들일 경우 사건의 경우의 수는 곱의 법칙으로 계산할 수 있습니다.

[곱의 법칙(Multiplication rule)]

두 개의 독립된 사건인 m과 n의 시행에서 이루어질 수 있는 경우의 수는 m·n입니다.

0 ∼ 9의 수 중에서 4개의 수를 선택하는 경우 각 자리에 올 수 있는 경우는 10개이므로 생성될 수 있는 모든 경우의 수는 식 2와 같습니다.

10 · 10 · 10 · 10 = 104

(식 2)

그러나 추출하는 4개의 수가 서로 다른수로 구성되는 경우 각 자리에 오는 수가 서로 다른 것으로 한다면 각 자리의 경우의 수는 처음 자리에 10개, 다음 자리에 9개, 3번째 자리는 8개, 그리고 마지막 자리는 7개입니다. 그러므로 4개 자리에 올 수 있는 모든 경우의 수는 식 3과 같이 계산됩니다.

10 · 9 · 8 · 7 = 5040

(식 3)

위 식들의 계산 과정은 식 4와 같이 변형할 수 있습니다.

10·9·8…1	=	10!	(식 4)
6·5·4…1		(10 − 4)!
	=	10·9·8·7

모집단 또는 샘플에서 순서를 고려하여 일부 또는 전부를 선택하는 경우의 수를 순열(permutation)이라 합니다.

[순열(permutation)]

순서를 고려하여 중복없이 n개 중에서 서로 다른 k개를 선택하는 경우의 수는 _nP_k로 나타내며 식 5와 같이 정의됩니다.

$$_nP_j=\frac{n!}{(n-k)!}$$

(식 5)

계승(factorial)은 numpy.math 클래스의 factorial() 함수를 사용합니다. 또한 scipy.special 클래스의 perm() 함수로 순열을 직접 계산할 수 있습니다.

• scipy.special.perm(n,k)
  • n개 중에서 k개를 선택하는 경우의 수(순열) 계산
• scipy.special.comb(n,k)
  • n개 중에서 중복없이 순서를 고려하지 않고 k개를 선택하는 경우의 수 (조합)

from numpy import math
math.factorial(10)/math.factorial(10-4)

5040.0

import scipy as sp
special.perm(10, 4)

5040.0

위의 순열은 나열되는 원소들의 순서가 고려되므로 1234와 2134 모두 포함합니다. 그러나 순서를 고려하지 않는다면 두 경우는 같은 것이 됩니다. 즉, 선택한 원소가 1,2,3,4를 포함하면 모두 같은 사건들로 간주되므로 이 조건을 고려해 주어야 합니다. 그 결과는 위 순열의 결과를 선택된 수들이 배열할 경우의 수로 나누어주면 됩니다. 이 과정은 식 6과 같이 일반화 할 수 있으며 조합(Combination)이라고 합니다.

[조합(Combination)]

순서를 고려하지 않고 n개 중에서 서로 다른 k개를 선택하는 경우로 식 6과 같이 계산됩니다.

\begin{align}_nC_k&=\binom{n}{k}\\&=\frac{n!}{k!(n-k)!} \end{align}

(식 6)

조합은 scipy.spectial 모듈 함수 comb(n, k) 함수를 사용할 수 있습니다. 이 함수의 인수 n는 총수, k는 선택하기 위한 수로서 모두 정수입니다. 또한 n, k는 여러개의 정수로 이루어진 배열 객체로 전달할 수 있습니다. 예를 들어 10개중에서 4개를 선택하는 조합의 수는 다음과 같습니다.

math.factorial(10)/(math.factorial(4)*math.factorial(6))

210.0

special.comb(10, 4)

210.0