알고리즘) Permutation, Combination (순열, 조합)

Permutation, Combination (순열, 조합)

확률, 경우의수, 곱의법칙

Permutation 순열
: 서로다른 n개의 원소들중 r개를 중복없이 선택하여 순서있게 배열하는 경우
nPr = n * (n-1) * ... * (n-r+1) = n! / (n-r)!

Combination 조합
: 서로다른 n개의 원소들중 r개를 중복없이 선택하는 경우. (순서없음)
nCr = nPr / r! = n! / r!(n-r)!

• 성질1 : nCr = nCn-r
• 성질2 : nCr = n-1Cr-1 + n-1Cr from 파스칼의 삼각형

파스칼의 삼각형 (n, r = 0부터 시작)

=> 이를 이용해 동적계획법으로 풀기도 한다.

Debugging) DP_bottom up & 파스칼의 삼각형 이용

• 큰수에서의 1000007은 일단 무시
• j=0이면 맨처음엔 1을 넣어주고, 이후로 점화식 합을 통해 값을 구한다. 이때, j=i일때인 마지막값에선 comb[1][2]와 같은형태로 정의되지않은 데이터이므로 int[]배열 초기값인 0이 들어가서 정상적으로 파스칼 삼각형을 구현하고 있음.

Input	Output
첫줄에질문의수 Q가주어집니다. (1 ≤ Q ≤ 100,000) 둘째줄부터 Q개의줄에걸쳐두개의숫자 n과 r이주어집니다. (0 ≤ n ≤ 1,000, 0 ≤ r ≤ n)	nCr의결과값을 1,000,007로 나눈 나머지 값을 출력합니다.

import java.util.*;

public class Test {
    static int comb[][] = new int[1001][1001];

    public static void calc_combination() {
        comb[0][0] = 1;
        //System.out.println("(0,0)=1");
        for (int i = 1; i <= 1000; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    comb[i][j] = 1;
                    //System.out.printf("(%d,%d)=%d ", i, j, comb[i][j]);
                } else {
                    comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % 1000007;
                    //System.out.printf("(%d,%d)=%d ", i, j, comb[i][j]);
                }
            }
            //System.out.println();
        }
    }

    public static void main(String args[]) {
        calc_combination();

        Scanner sc = new Scanner(System.in);

        int q = sc.nextInt();
        while (q-- > 0) {
            int n = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(comb[n][r]);
        }
    }
}

---

Permutation 순열

http://www.eandbsoftware.org/print-all-permutations-of-a-given-string/

public class Permutation {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        perm(arr, 0, 4, 4);
    }

    public static void perm(int[] arr, int depth, int n, int k) {
        if (depth == k) {
            print(arr, k);
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(arr, depth, i);
            System.out.println("swap1: " + depth + "," + i);
            perm(arr, depth + 1, n, k);
            swap(arr, depth, i);
            System.out.println("swap2: " + depth + "," + i);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void print(int[] arr, int k) {
        for (int i = 0; i < k; i++) {
            if (i == k - 1) System.out.println(arr[i]);
            else System.out.print(arr[i] + ",");
        }
    }
}

출처

순열(Permutation) 알고리즘

수열의 순열과 조합 출력하기(nPr, nCr)