기초수학 - 조합(Combination)

조합(Combination).

조합(Combination)은 주어진 원소들 중에서 일부를 선택하여 만들어지는 모든 경우의 수를 구하는 것을 말합니다. 
조합은 순서가 중요하지 않으며, 중복된 원소를 포함하지 않습니다. 
일반적으로 조합은 "n 개 중에서 r 개를 선택하는 경우의 수"를 나타내는 nCr로 표기됩니다.

조합을 구하는 방법에는 여러 가지 방법이 있지만, 
가장 일반적인 방법은 재귀적으로 구현하는 것입니다. 
재귀적인 방법을 사용하면 간결하고 직관적으로 조합을 구할 수 있습니다.

- 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X)
case1. 서로 다른 4명 중 주번을 2명 뽑는 방법

public class CombinationTest1 {
    public static void main(String[] args) {
        // 조합 - 서로 다른 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); // 6
    }
}

 

중복조합(Combination with repetition).

중복 조합(Combination with repetition)은 주어진 원소들 중에서 중복을 허용하여 조합을 구성하는 것을 말합니다. 
하나의 원소를 여러 번 선택할 수 있고, 순서는 고려하지 않는 조합입니다.

중복 조합은 원소의 개수가 많아지거나 원소의 중복 선택이 필요한 경우 유용하게 사용될 수 있습니다.
중복 조합을 구현하는 방법은 다양하지만, 일반적으로는 재귀 함수를 활용하여 구현할 수 있습니다.

- 서로 다른 n개 중에서 r개를 선택하는 경우의 수(순서 X, 중복 O)
case1. 후보 2명, 유권자 3명일 때 무기명 투표하는 방법

package june2023.day04;

public class CombinationTest1 {
    public 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) {

        // 후보 2명, 유권자 3명 유기명 투표 경우의 수
        int n = 2;
        int r = 3;
        System.out.println(getCombination(n + r - 1, r)); // 4
    }
}

 

---

package june2023.day04;
// 1, 2, 3, 4, 를 이용하여 세자리 자연수를 만드는 방법(순서 X, 중복 X) 결과 출력

public class CombinationTest2 {
    static 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);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = {false, false, false, false};

        combination(arr, visited, 0, 4, 3);
    }
}

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

 

---

정리.

순열(Permutation):
순열은 주어진 원소들로 가능한 모든 순서를 고려하여 조합하는 것을 말합니다. 즉, 순서를 고려하며 원소를 선택하고 배열하는 경우를 모두 고려합니다. 예를 들어, 3개의 원소 [A, B, C]가 주어졌을 때, 이를 이용해 만들 수 있는 순열은 [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A]로 총 6개가 있습니다. 순열의 경우 원소의 순서가 다르면 다른 조합으로 취급합니다.

중복 순열(Permutation with repetition):
중복 순열은 주어진 원소들 중에서 중복을 허용하여 순서를 고려하여 조합하는 것을 말합니다. 즉, 하나의 원소를 여러 번 선택할 수 있고, 순서도 고려합니다. 예를 들어, 2개의 원소 [A, B]가 주어졌을 때, 중복 순열로 만들 수 있는 조합은 [A, A], [A, B], [B, A], [B, B]로 총 4개가 있습니다. 중복 순열에서는 같은 원소라도 위치에 따라 다른 조합으로 취급합니다.

원순열(Circular Permutation):
원순열은 순열의 한 종류로, 원형으로 배열된 원소들 중에서 가능한 모든 순서를 고려하여 조합하는 것을 말합니다. 즉, 원형으로 배열된 원소들을 시작점을 달리하여 순서대로 조합합니다. 예를 들어, 3개의 원소 [A, B, C]가 원형으로 배열되어 있을 때, 원순열로 만들 수 있는 조합은 [A, B, C], [B, C, A], [C, A, B]로 총 3개가 있습니다. 원순열에서는 순서를 달리하여도 같은 조합으로 간주합니다.

조합(Combination):
조합은 주어진 원소들 중에서 순서를 고려하지 않고 조합하는 것을 말합니다. 즉, 선택된 원소들로만 조합을 구성하며, 순서는 고려하지 않습니다. 예를 들어, 3개의 원소 [A, B, C]가 주어졌을 때, 이를 이용해 만들 수 있는 조합은 [A, B], [A, C], [B, C]로 총 3개가 있습니다. 조합에서는 원소의 순서가 다르더라도 같은 조합으로 취급합니다.

중복 조합(Combination with repetition):
중복 조합은 주어진 원소들 중에서 중복을 허용하여 조합을 구성하는 것을 말합니다. 즉, 하나의 원소를 여러 번 선택할 수 있고, 순서는 고려하지 않는 조합입니다. 예를 들어, 2개의 원소 [A, B]가 주어졌을 때, 중복 조합으로 만들 수 있는 조합은 [A, A], [A, B], [B, B]로 총 3개가 있습니다. 중복 조합에서는 같은 원소라도 위치에 따라 다른 조합으로 취급합니다.