[기초 알고리즘] 수학: 조합

1. K-Combination

• k개의 원소들을 사용해서, 순서를 고려하지 않고 배열한 모든 경우의 수

 

순열의 수

• ${\displaystyle C(n,r)={\frac {n(n-1)\cdots (n-r+1)}{r!}}={\frac {n!}{r!(n-r)!}}}$

 

성질

대칭성

• n개의 원소에서 r개를 선택하는 것과 (n-r)개를 선택하는 방법의 수가 동일합니다.
• ${\displaystyle {\binom {n}{r}}={\binom {n}{n-r}}}$

 

재귀적 (파스칼의 삼각형)

• 두 집합의 합
  • 원래 집합에서 하나의 원소를 제외하고, r개를 선택하는 방법의 수
  • 원래 집합에서 하나의 원소를 제외하고, r-1개를 선택하는 방법의 수
• ${\displaystyle {\binom {n}{r}}={\binom {n-1}{r}}+{\binom {n-1}{r-1}}}$

mul[0] = 1;
for (int r = 1; r < n; r++) mul[r] = mul[r-1] * (n-r) / r;

 

생성함수

• ${\displaystyle (1+x)^{n}=\sum _{r=0}^{n}{\binom {n}{r}}x^{r}}$

 

예

• 책 빌리기
• 파티 초대
• 팀 만들기

 

코드

private void comb(int k, int depth, int start) {
    if (depth == k) {
        System.out.println(Arrays.toString(choosed));
        return;
    }

    for (int i = start; i < src.length; i++) {
        choosed[depth] = src[i];
        comb(k, depth+1, i+1);
    }
}

 

2. Duplicate Combination

• k개의 원소들을 사용해서, 중복을 허용하여 만든 조합

 

순열의 수

• ${\displaystyle \left(\!\!\!{\binom {n}{r}}\!\!\!\right)}$
• ${\displaystyle {\binom {n+r-1}{r}}={\binom {n+r-1}{n-1}}=(-1)^{r}{\binom {-n}{r}}}$

 

생성 함수

• ${\displaystyle (1-x)^{-n}=\sum _{r=0}^{\infty }{\binom {-n}{r}}(-x)^{r}=\sum _{r=0}^{\infty }{\binom {n+r-1}{r}}x^{r}}$

 

예

• 과자 번들 종류
• 파인트 아이스크림 구성

 

코드

private void combDup(int k, int depth, int start) {
    if (depth == k) {
        System.out.println(Arrays.toString(choosed));
        return;
    }

    for (int i = start; i < src.length; i++) {
        choosed[depth] = src[i];
        comb(k, depth+1, i);
    }
}

 

 

출처

• Wiki - Combination