조합

조합

조합 (Combination) 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X)
예시) 서로 다른 4명 중 주번 2명 뽑는 방법
n𝐶r =𝑛!/(𝑛−𝑟)!𝑟!=𝑛𝑃𝑟/𝑟! 단, 0<𝑟≤𝑛

중복 조합

서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 O)
예시) 후보 2명, 유권자 3명일 때 무기명 투표 방법
𝑛𝐻𝑟=𝑛+𝑟−1𝐶𝑟

public class Practice4 {

    static int getCombination(int n, int r) {
        int pResult = 1;
        for (int i = n; i >= n - r + 1; i--) {
            pResult *= i;
        }

        int rResult = 1;
        for (int i = 1; i <= r; i++) {
            rResult *= i;
        }

        return pResult / rResult;
    }

    public static void main(String[] args) {
        //1.    조합
        System.out.println("== 조합 ==");
        //서로 다른 4명 중 주번 2명 뽑는 경우의 수
        int n = 4;
        int r = 2;

        int pResult = 1;
        for (int i = n; i >= n - r + 1; i--) {
            pResult *= i;
        }

        int rResult = 1;
        for (int i = 1; i <= r; i++) {
            rResult *= i;
        }
        System.out.println("결과 : " + pResult / rResult);

        //2.    중복 조합
        System.out.println("== 중복 조합 ==");
        //후보 2명, 유권자 3명일 때 무기명 투표 경우의 수
        n = 2;
        r = 3;

        System.out.println("결과 : " + getCombination(n + r - 1, r));
    }
}

== 조합 ==
결과 : 6
== 중복 조합 ==
결과 : 4

//1,2,3,4를 이용하여 세자리 자연수를 만드는 방법(순서x, 중복x)의 각 결과를 출력.
public class Practice4_1 {
    public static void main(String[] args) {
        //Test Code
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = {false, false, false, false};

        Practice4_1 p = new Practice4_1();
        p.combination(arr, visited, 0, 4, 3);
    }

    private void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        if (depth == n) {
            return;
        }

        visited[depth] = true;
        combination(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        combination(arr, visited, depth + 1, n, r);
    }
}

1 2 3 
1 2 4 
1 3 4 
2 3 4 

// Initial call
combination(arr, visited, 0, 4, 3)
// depth = 0, r = 3

visited[0] = true;  // visited = [true, false, false, false]
combination(arr, visited, 1, 4, 2)
// depth = 1, r = 2

visited[1] = true;  // visited = [true, true, false, false]
combination(arr, visited, 2, 4, 1)
// depth = 2, r = 1

visited[2] = true;  // visited = [true, true, true, false]
combination(arr, visited, 3, 4, 0)
// depth = 3, r = 0
// Output: 1 2 3

visited[2] = false;  // visited = [true, true, false, false]
combination(arr, visited, 3, 4, 1)
// depth = 3, r = 1

visited[3] = true;  // visited = [true, true, false, true]
combination(arr, visited, 4, 4, 0)
// depth = 4, r = 0
// Output: 1 2 4

visited[3] = false;  // visited = [true, true, false, false]
combination(arr, visited, 4, 4, 1)
// depth = 4, r = 1
// No output (base case reached)

visited[1] = false;  // visited = [true, false, false, false]
combination(arr, visited, 2, 4, 2)
// depth = 2, r = 2

visited[2] = true;  // visited = [true, false, true, false]
combination(arr, visited, 3, 4, 1)
// depth = 3, r = 1

visited[3] = true;  // visited = [true, false, true, true]
combination(arr, visited, 4, 4, 0)
// depth = 4, r = 0
// Output: 1 3 4

visited[3] = false;  // visited = [true, false, true, false]
combination(arr, visited, 4, 4, 1)
// depth = 4, r = 1
// No output (base case reached)

visited[2] = false;  // visited = [true, false, false, false]
combination(arr, visited, 3, 4, 2)
// depth = 3, r = 2

visited[3] = true;  // visited = [true, false, false, true]
combination(arr, visited, 4, 4, 1)
// depth = 4, r = 1
// No output (base case reached)

visited[3] = false;  // visited = [true, false, false, false]
combination(arr, visited, 4, 4, 2)
// depth = 4, r = 2
// No output (base case reached)

visited[0] = false;  // visited = [false, false, false, false]
combination(arr, visited, 1, 4, 3)
// depth = 1, r = 3

visited[1] = true;  // visited = [false, true, false, false]
combination(arr, visited, 2, 4, 2)
// depth = 2, r = 2

visited[2] = true;  // visited = [false, true, true, false]
combination(arr, visited, 3, 4, 1)
// depth = 3, r = 1

visited[3] = true;  // visited = [false, true, true, true]
combination(arr, visited, 4, 4, 0)
// depth = 4, r = 0
// Output: 2 3 4

visited[3] = false;  // visited = [false, true, true, false]
combination(arr, visited, 4, 4, 1)
// depth = 4, r = 1
// No output (base case reached)

visited[2] = false;  // visited = [false, true, false, false]
combination(arr, visited, 3, 4, 2)
// depth = 3, r = 2

visited[3] = true;  // visited = [false, true, false, true]
combination(arr, visited, 4, 4, 1)
// depth = 4, r = 1
// No output (base case reached)

visited[3] = false;  // visited = [false, true, false, false]
combination(arr, visited, 4, 4, 2)
// depth = 4, r = 2
// No output (base case reached)

visited[1] = false;  // visited = [false, false, false, false]
combination(arr, visited, 2, 4, 3)
// depth = 2, r = 3

visited[2] = true;  // visited = [false, false, true, false]
combination(arr, visited, 3, 4, 2)
// depth = 3, r = 2

visited[3] = true;  // visited = [false, false, true, true]
combination(arr, visited, 4, 4, 1)
// depth = 4, r = 1
// No output (base case reached)

visited[3] = false;  // visited = [false, false, true, false]
combination(arr, visited, 4, 4, 2)
// depth = 4, r = 2
// No output (base case reached)

visited[2] = false;  // visited = [false, false, false, false]
combination(arr, visited, 3, 4, 3)
// depth = 3, r = 3

visited[3] = true;  // visited = [false, false, false, true]
combination(arr, visited, 4, 4, 2)
// depth = 4, r = 2
// No output (base case reached)

visited[3] = false;  // visited = [false, false, false, false]
combination(arr, visited, 4, 4, 3)
// depth = 4, r = 3
// No output (base case reached)

출처 : 제로베이스