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

순열과 조합 (Permutation & Combination)

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

\begin{aligned} 1 : [\begin{array}{c} 1 \\ 2 \\ ⋮ \\ 6 \end{array}] & \Rightarrow [\begin{array}{c} (1, 1) \\ (1, 2) \\ ⋮ \\ (1, 6) \end{array}] \\ 2 : [\begin{array}{c} 1 \\ 2 \\ ⋮ \\ 6 \end{array}] & \Rightarrow [\begin{array}{c} (2, 1) \\ (2, 2) \\ ⋮ \\ (2, 6) \end{array}] \\ ⋮ \end{aligned}

(식 1)

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

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

len(S)

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

[곱의 법칙(Multiplication rule)]

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

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

10 · 10 · 10 · 10 = 10⁴

(식 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와 같이 정의됩니다.

_{n} P_{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{aligned} _{n} C_{k} & = (\binom{n}{k}) \\ = \frac{n!}{k! (n - k)!} \end{aligned}

(식 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

[Linear Algebra] 유사변환(Similarity transformation)

유사변환(Similarity transformation) n×n 차원의 정방 행렬 A, B 그리고 가역 행렬 P 사이에 식 1의 관계가 성립하면 행렬 A와 B는 유사행렬(similarity matrix)이 되며 행렬 A를 가역행렬 P와 B로 분해하는 것을 유사 변환(similarity transformation) 이라고 합니다.

\begin{matrix} (1) & A = P B P^{- 1} \Leftrightarrow P^{- 1} A P = B \end{matrix}

식 2는 식 1의 양변에 B의 고유값을 고려한 것입니다.

\begin{aligned} (식 2) & B - λ I & = P^{- 1} A P - λ P^{- 1} P \\ = P^{- 1} (A P - λ P) \\ = P^{- 1} (A - λ I) P \end{aligned}

식 2의 행렬식은 식 3과 같이 정리됩니다.

\begin{aligned} \begin{aligned} det (B - λ I) & = det (P^{- 1} (A P - λ P)) \\ = det (P^{- 1}) det ((A - λ I)) det (P) \\ = det (P^{- 1}) det (P) det ((A - λ I)) \\ = det (A - λ I) \end{aligned} \\ \begin{aligned} ∵ det (P^{- 1}) det (P) & = det (P^{- 1} P) \\ = det (I) \end{aligned} \end{aligned}

유사행렬의 특성 유사행렬인 두 정방행렬 A와 B는 'A ~ B' 와 같...

[sympy] Sympy객체의 표현을 위한 함수들

Sympy객체의 표현을 위한 함수들 General simplify(x): 식 x(sympy 객체)를 간단히 정리 합니다. import numpy as np from sympy import * x=symbols("x") a=sin(x)**2+cos(x)**2 a

\sin^{2} (x) + \cos^{2} (x)

simplify(a) 1 simplify(b)

\frac{x^{3} + x^{2} - x - 1}{x^{2} + 2 x + 1}

simplify(b) x - 1 c=gamma(x)/gamma(x-2) c

\frac{Γ (x)}{Γ (x - 2)}

simplify(c)

(x - 2) (x - 1)

위의 예들 중 객체 c의 감마함수(gamma(x))는 확률분포 등 여러 부분에서 사용되는 표현식으로 다음과 같이 정의 됩니다. 감마함수는 음이 아닌 정수를 제외한 모든 수에서 정의됩니다. 식 1과 같이 자연수에서 감마함수는 factorial(!), 부동소수(양의 실수)인 경우 적분을 적용하여 계산합니다.

\begin{matrix} (식 1) & Γ (n) = {\begin{cases} (n - 1)! & n : 자연수 \\ \int_{0}^{\infty} x^{n - 1} e^{- x} d x & n : 부동소수 \end{cases} \end{matrix}

x=symbols('x') gamma(x).subs(x,4)

6

factorial 계산은 math.factorial() 함수를 사용할 수 있습니다. import math math.factorial(3) 6 a=gamma(x).subs(x,4.5) a.evalf(3) 11.6 simpilfy() 함수의 알고리즘은 식에서 공통사항을 찾아 정리하...

sympy.solvers로 방정식해 구하기

sympy.solvers로 방정식해 구하기 대수 방정식을 해를 계산하기 위해 다음 함수를 사용합니다. sympy.solvers.solve(f, *symbols, **flags) f=0, 즉 동차방정식에 대해 지정한 변수의 해를 계산 f : 식 또는 함수 symbols: 식의 해를 계산하기 위한 변수, 변수가 하나인 경우는 생략가능(자동으로 인식) flags: 계산 또는 결과의 방식을 지정하기 위한 인수들 dict=True: {x:3, y:1}같이 사전형식, 기본값 = False set=True :{(x,3),(y,1)}같이 집합형식, 기본값 = False ratioal=True : 실수를 유리수로 반환, 기본값 = False positive=True: 해들 중에 양수만을 반환, 기본값 = False 예

x^{2} = 1

의 해를 결정합니다. solve() 함수에 적용하기 위해서는 다음과 같이 식의 한쪽이 0이 되는 형태인 동차식으로 구성되어야 합니다.

x^{2} - 1 = 0

import numpy as np from sympy import * x = symbols('x') solve(x**2-1, x) [-1, 1] 위 식은 계산 과정은 다음과 같습니다.

\begin{array}{r} x^{2} - 1 = 0 \to (x + 1) (x - 1) = 0 \\ x = 1 or - 1 \end{array}

예

x^{4} = 1

의 해를 결정합니다. solve() 함수의 인수 set=True를 지정하였으므로 결과는 집합(set)형으로 반환됩니다. eq=x**4-1 solve(eq, set=True) ([x], {(-1,), (-I,), (1,), (I,)}) 위의 경우 I는 복소수입니다.즉 위 결과의 과정은 다음과 같습니다.

x^{4} - 1 = (x^{2} + 1) (x + 1) (x - 1) = 0 \to x = \pm \sqrt{- 1}, \pm 1 = \pm i, \pm 1

실수...

sons dataStory

이 블로그 검색

[matplotlib] 등고선(Contour)