[Java] 조합, 중복조합을 구해주는 클래스

알고리즘을 풀다 보면 간혹 조합을 직접 만들어서 사용해야 할 때가 있었는데 그럴 때마다 새로 만들기 귀찮아서 범용 객체를 이번 기회에 만들어봤다.

제네릭을 사용해서 문자열, 숫자(Integer, Double)등 모두 포괄할 수 있도록 설계했다.

 

조합은 getCombination, 중복조합은 getRepeatableCombination 을 호출하면 되고 파라미터 arr은 후보군들을 제네릭 리스트로, r은 그중 몇 개를 뽑을지를 전달한다.

 

결괏값으로는 후보군 중 r개를 뽑아서 만들어진 리스트들을 리스트로 (2중 리스트)로 리턴한다.

public class Combination {
    public static <T> List<List<T>> getCombination(List<T> arr, int r) {
        boolean[] visited = new boolean[arr.size()];
        List<List<T>> result = new ArrayList<>();
        normalCombination(arr, visited, 0, arr.size(), r, result);
        return result;
    }
    private static <T> void normalCombination(List<T> arr, boolean[] visited, int start, int n, int r, List<List<T>> result) {
        if (r == 0) {
            List<T> temp = new ArrayList<>();
            for (int i = 0; i < n; i++) if (visited[i]) temp.add(arr.get(i));
            result.add(temp);
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            normalCombination(arr, visited, i + 1, n, r - 1, result);
            visited[i] = false;
        }
    }

    public static <T> List<List<T>> getRepeatableCombination(List<T> arr, int r) {
        List<List<T>> result = new ArrayList<>();
        repeatableCombination(arr, new Object[r], 0, 0, r, result);
        return result;
    }
    private static <T> void repeatableCombination(List<T> arr, Object[] out, int start, int depth, int r, List<List<T>> result) {
        if (depth == r) {
            List<T> temp = new ArrayList<>();
            for (Object o : out) temp.add((T) o);
            result.add(temp);
            return;
        }
        for (int i = start; i < arr.size(); i++) {
            out[depth] = arr.get(i);
            repeatableCombination(arr, out, i, depth + 1, r, result);
        }
    }
}