가능한 실행순서의 개수 유도하기 [쏙쏙 들어오는 함수형 코딩]

Eric Normand 의 책 "쏙쏙 들어오는 함수형 코딩(grokking simplicity)" 의 '가능한 실행순서의 개수' 공식을 유도해봅니다.

개요

가능한 실행순서의 개수 공식은 다음과 같습니다.

 

$$o =\frac{(t\cdot a)!}{(a!)^t}$$

 

$t$ 는 타입라인의 개수이고, $a$는 액션의 개수입니다.

위 공식은 아래 그림과 같이 각 타임라인이 모두 같은 수의 액션을 가지고 있을 때 적용 가능합니다. (타임라인마다 액션의 수가 다를 수 있는데, 그 부분을 책에서 설명해주지 않은 것 같아보입니다.)

3개의 타임라인, 2개의 액션을 갖는 각각의 타임라인

위와 같은 경우 $t=3$, $a=2$ 로 적용 가능하며, 가능한 실행순서의 개수 $o=90$ 입니다.

가령 다음과 같은 타임라인이라면 위 공식을 적용할 수는 없습니다.

2개의 액션, 3개의 액션, 4개의 액션을 갖는 각각의 타임라인

책의 공식 $(t \cdot a)!/(a!)^t$ 에는 바로 대입할 수 없지만, 각 타임라인의 액션의 개수가 다른 경우(일반적인 경우)에도 가능한 실행순서의 개수를 계산할 수 있습니다. 미리 계산해보면 다음과 같습니다. ($a_t$는 t 번째 타임라인의 액션의 개수를 의미합니다.)

 

$$\frac{(a_1+a_2+\cdots+a_n)!}{a_1!\cdot a_2!\cdot a_3!\times  \cdots \times a_n!}$$

 

$$\frac{(2 + 3 + 4)!}{2!\times3!\times4!} = \frac{9!}{2!\cdot3!\cdot4!} = 1260$$

 

반응형

 

두 개의 타임라인에서 가능한 실행순서의 개수

두 타임라인에서 액션이 교차될 수 있는 가능성

C 액션은 왼쪽 타임라인의 $\alpha, \beta, \gamma$ 영역 중에 한 부분에 들어갈 수 있습니다.

D 액션도 C 와 마찬가지로 $\alpha, \beta, \gamma$ 영역 중에 한 부분에 들어갈 수 있습니다.

결국 오른쪽 타임라인의 액션의 수만큼 $\alpha, \beta, \gamma$ 영역을 선택하는 문제로 치환할 수 있습니다.

→ 즉, $\alpha, \beta, \gamma$ 중에 2개를 순서에 관계 없이 중복해서 선택하는 문제로 볼 수 있습니다.

(순서에 관계가 없는 이유는 2개를 정하기만 하면, 순서는 C → D 순서로 확정되기 때문입니다.)

이는 중복조합입니다.

 

$${}_3{\rm H}_2$$

 

여기서 3 은 왼쪽 타임라인 액션의 개수 + 1 이며, 2는 오른쪽 타임라인 액션의 개수입니다.

액션의 개수를 일반화하면 다음과 같이 기술할 수 있습니다.

 

$${}_{l+1}{\rm H}_{r} = {}_{l+r}{\rm C}_{r} $$

 

• $l$: 왼쪽 타임라인의 액션 수
• $r$: 오른쪽 타임라인의 액션 수

3 개의 타임라인에서 가능한 실행순서의 개수

2개의 타임라인이 각각 2개의 액션을 가질 때 조합될 수 있는 경우의 수

각각 2개의 액션을 가진 2개의 타임라인의 가능한 실행순서의 개수는 위에서 살펴본 것과 같이 ${}_3{\rm H}_2 = 6$ 가지입니다.

결과적으로 하나의 타임라인으로 합쳐서 생각해본다면, 총 4개의 액션으로 구성된 타임라인이 됩니다.

이를 3번째 타임라인과 가능한 실행순서의 개수를 다음과 같이 조합해볼 수 있습니다.

4개의 액션을 갖는 타임라인과 2개의 액션을 갖는 타임라인이 서로 조합되어 가능한 경우의 수

3번째 타임라인의 액션이 기존 액션의 사이 사이 영역에 들어갈 수 있는 경우의 수는 ${}_5{\rm H}_2 = 15$ 가지이며, 이는 1번과 2번 타임라인만으로 가능했던 조합인 6가지와 곱하여 총 90가지의 경우의 수를 가지게 됨을 알 수 있습니다.

n 개의 타임라인에서 가능한 실행순서의 개수(일반)

n개의 타임라인이 각각 임의의 개수의 액션을 가질 때

$${}_{a_1+1}{\rm H}_{a_2}\times{}_{a_1+a_2+1}{\rm H}_{a_3}\times \cdots \times {}_{a_1+a_2+\cdots+a_{n-1}+1}{\rm H}_{a_n}$$
$${\rm \prod_{t=2}^{n}} {}_{1+\Sigma_{i=1}^{t-1}a_{i}}{\rm H}_{a_t}$$
$${\rm \prod_{t=2}^{n}} {}_{(a_{t}-1)+1+\Sigma_{i=1}^{t-1}a_{i}}{\rm C}_{a_t}$$
$${\rm \prod_{t=2}^{n}} {}_{\Sigma_{i=1}^{t}a_{i}}{\rm C}_{a_t}$$
$${}_{a_1+a_2}{\rm C}_{a_2}\times{}_{a_1+a_2+a_3}{\rm C}_{a_3}\times \cdots \times {}_{a_1+a_2+\cdots+a_{n}}{\rm C}_{a_n}$$
$$\frac{(a_1+a_2)!}{a_2!\cdot(a_1)!}\times\frac{(a_1+a_2+a_3)!}{a_3!\cdot(a_1+a_2)!}\times\cdots\times\frac{(a_1+a_2+\cdots+a_n)!}{a_n!\cdot(a_1+a_2+\cdots+a_{n-1})!}$$
$$\frac{\cancel{(a_1+a_2)!}}{a_2!\cdot(a_1)!}\times\frac{\cancel{(a_1+a_2+a_3)!}}{a_3!\cdot\cancel{(a_1+a_2)!}}\times\cdots\times\frac{(a_1+a_2+\cdots+a_n)!}{a_n!\cdot\cancel{(a_1+a_2+\cdots+a_{n-1})!}}$$

$$\frac{1}{a_2!\cdot(a_1)!}\times\frac{1}{a_3!}\times\cdots\times\frac{(a_1+a_2+\cdots+a_n)!}{a_n!}$$

$$\frac{(a_1+a_2+\cdots+a_n)!}{a_1!\cdot a_2!\cdot a_3!\times  \cdots \times a_n!}$$

 

n 개의 타임라인이 각각 $a_n$ 개의 (n 은 타임라인의 순번) 액션을 갖는 경우 가능한 실행순서의 개수를 구하는 공식이 유도되었습니다.

n 개의 타임라인이 모두 a 개의 액션을 가진다면(특수)

타임라인의 수만큼의 자연수 n 에 대해서 $a_1 = a_2 = \cdots = a_n = a$ 이라고 할 수 있으므로

 

$$\frac{(a_1+a_2+\cdots+a_n)!}{a_1!\cdot a_2!\cdot a_3!\times \cdots \times a_n!} = \frac{(\overbrace{a+a+\cdots+a}^n) !}{\underbrace{a!\cdot a!\cdot a!\times \cdots \times a!}_n} = \frac{(n \cdot a)!}{(a!)^n}$$

 

여기서 타임라인의 개수인 n 을 책에서 표현된 타임라인의 개수 t 로만 바꾸어주면 책과 동일한 형태의 가능한 실행순서의 개수가 됩니다.

 

$$\frac{(t\cdot a)!}{(a!)^t} \quad {}_\blacksquare$$