[수학]Permutation & Combination

Permutation & Combination

순열과 조합 알고리즘

순열 : 서로 다른 n개에서 r개를 순서대로 나열하는 경우의 수
조합 : 서로 다른 n개에서 r개를 순서없이 고르는 경우의 수

순서

10장의 트럼프 카드에서 1, 5, 8의 카드를 뽑은 상황을 가정한다.
순서없는 경우 : 1을 먼저 뽑건, 5를 먼저 뽑건, 상관하지 않는다.
순서있는 경우 : 1을 먼저 뽑는 경우, 5를 먼저 뽑는 경우, 8을 먼저 뽑는 경우를 모두 고려한다.

순열 예시 코드

nPr : n (n - 1) (n - 2) * ... (n - r - 1)

#define MOD 1000000007

long long permutation(int n, int r){
    long long ans = 1;
    for(int i = n; i >= n - r - 1; i--){
        ans *= i;
        ans %= MOD;
    }
    return ans;
}

조합 예시 코드

nCr : nPr / r!
조합의 성질인 파스칼의 삼각형을 이용해서 메모이제이션을 활용하면
nCr = n-1Cr-1 + n-1Cr

#define MOD 1000000007
#define MAX 100000

long long combi[MAX][MAX];

void init(){
    combi[0][0] = 1;
    for(int i = 1; i <= MAX; i++){
        combi[i][0] = 1;
        for(int j = 1; j <= i; j++)    
            combi[i][j] = (combi[i - 1][j - 1] + combi[i - 1][j]) % MOD;
    }
}