조합

조합이란

nCr

수학에서의 조합(Combination)은 주어진 원소들 중에서 일부를 선택하여 순서에 상관없이 조합을 만드는 것을 말합니다. 조합은 선택된 원소들의 집합을 의미하며, 선택된 원소들의 순서는 고려하지 않습니다.

조합은 보통 "n 개 중에서 r 개를 선택하는 조합"으로 표현됩니다. 이는 n개의 원소가 있을 때, 그 중에서 r개를 선택하여 만들 수 있는 모든 부분집합을 의미합니다. 조합의 수를 구할 때는 주로 이항 계수(Binomial Coefficient)를 사용합니다.

중복조합

nHr

중복조합(Combination with Repetition)은 주어진 원소들 중에서 중복을 허용하여 원하는 개수만큼 선택하여 조합을 만드는 것을 말합니다.

일반적으로 조합은 중복을 허용하지 않는 조합(조합론적 조합)과 중복을 허용하는 조합(중복조합)으로 나뉩니다. 중복을 허용하지 않는 조합은 한 번 선택한 원소는 다시 선택할 수 없습니다. 예를 들어, 숫자 1, 2, 3 중에서 2개를 선택하는 조합은 {1, 2}, {1, 3}, {2, 3}입니다.

중복을 허용하는 조합은 한 번 선택한 원소를 다시 선택할 수 있습니다. 예를 들어, 숫자 1, 2, 3 중에서 2개를 선택하는 중복조합은 {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}입니다.

구현 방법

조합

1. 재귀

import java.util.ArrayList;
import java.util.List;

public class CombinationGenerator {
    /**
     * 조합을 생성하는 메소드입니다.
     *
     * @param nums 주어진 숫자 배열
     * @param k    선택할 원소의 개수
     * @return 생성된 조합의 리스트
     */
    public static List<List<Integer>> generateCombinations(int[] nums, int k) {
        List<List<Integer>> result = new ArrayList<>();

        // 현재 조합을 저장하는 리스트
        List<Integer> current = new ArrayList<>();

        // 조합 생성을 위한 재귀 함수 호출
        generate(nums, k, 0, current, result);

        return result;
    }

    /**
     * 재귀 함수를 통해 조합을 생성합니다.
     *
     * @param nums    주어진 숫자 배열
     * @param k       선택할 원소의 개수
     * @param start   조합 생성의 시작 위치
     * @param current 현재 조합을 저장하는 리스트
     * @param result  생성된 조합의 리스트
     */
    private static void generate(int[] nums, int k, int start, List<Integer> current, List<List<Integer>> result) {
        // 원소의 개수가 선택할 원소의 개수와 동일하면 조합을 추가하고 종료합니다.
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }

        // 현재 위치부터 순회하여 원소를 선택합니다.
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);

            // 다음 위치로 재귀 호출하여 조합을 생성합니다.
            generate(nums, k, i + 1, current, result);

            // 마지막으로 선택한 원소를 제거하여 다른 조합을 생성합니다.
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int k = 3;

        // 조합 생성
        List<List<Integer>> combinations = generateCombinations(nums, k);

        // 생성된 조합 출력
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
    }
}

2. 비트마스크

import java.util.ArrayList;
import java.util.List;

public class CombinationGenerator {
    public static List<List<Integer>> generateCombinations(int[] nums, int k) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        int max = 1 << n;

        for (int i = 0; i < max; i++) {
            if (Integer.bitCount(i) == k) {
                List<Integer> combination = new ArrayList<>();
                for (int j = 0; j < n; j++) {
                    if ((i & (1 << j)) != 0) {
                        combination.add(nums[j]);
                    }
                }
                result.add(combination);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int k = 3;
        List<List<Integer>> combinations = generateCombinations(nums, k);
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
    }
}

3. 라이브러리

import org.apache.commons.math3.util.CombinatoricsUtils;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class CombinationGenerator {
    public static List<List<Integer>> generateCombinations(int[] nums, int k) {
        List<List<Integer>> result = new ArrayList<>();
        Iterator<int[]> combinations = CombinatoricsUtils.combinationsIterator(nums.length, k);

        while (combinations.hasNext()) {
            int[] combination = combinations.next();
            List<Integer> current = new ArrayList<>();
            for (int index : combination) {
                current.add(nums[index]);
            }
            result.add(current);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int k = 3;
        List<List<Integer>> combinations = generateCombinations(nums, k);
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
    }
}

중복조합

1. 재귀

import java.util.ArrayList;
import java.util.List;

public class Combination {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int r = 2;
        List<List<Integer>> combinations = generateCombinations(nums, r);
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
    }

    public static List<List<Integer>> generateCombinations(int[] nums, int r) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> currentCombination = new ArrayList<>();
        generate(nums, r, 0, currentCombination, combinations);
        return combinations;
    }

    public static void generate(int[] nums, int r, int index, List<Integer> currentCombination, List<List<Integer>> combinations) {
        if (currentCombination.size() == r) {
            combinations.add(new ArrayList<>(currentCombination));
            return;
        }
        if (index >= nums.length) {
            return;
        }

        // 현재 인덱스의 숫자를 선택하고 재귀 호출
        currentCombination.add(nums[index]);
        generate(nums, r, index, currentCombination, combinations);

        // 현재 인덱스의 숫자를 선택하지 않고 재귀 호출
        currentCombination.remove(currentCombination.size() - 1);
        generate(nums, r, index + 1, currentCombination, combinations);
    }
}

2. 비트마스크

import java.util.ArrayList;
import java.util.List;

public class CombinationWithBitmask {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int r = 2;
        List<List<Integer>> combinations = generateCombinations(nums, r);
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
    }

    public static List<List<Integer>> generateCombinations(int[] nums, int r) {
        List<List<Integer>> combinations = new ArrayList<>();
        int n = nums.length;

        int combinationsCount = 1 << n; // 2의 n승

        for (int bitmask = 0; bitmask < combinationsCount; bitmask++) {
            if (Integer.bitCount(bitmask) == r) { // 선택된 원소 개수가 r인 경우에만 처리
                List<Integer> combination = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    if ((bitmask & (1 << i)) > 0) {
                        combination.add(nums[i]);
                    }
                }
                combinations.add(combination);
            }
        }

        return combinations;
    }
}

3. 라이브러리
생략