[Java Algorithm Note] 조합 (feat. 재귀)

저번 순열에 이어 이번에는 조합에 대해 정리해보려 한다.

(순열 정리는 아래 참고! 👇)

https://seolhee2750.tistory.com/229

[Java Algorithm Note] 순열 (feat. 재귀)

 

📎 조합

조합은 서로 다른 n개의 원소에서 r개를 순서에 상관하지 않고 선택 혹은 나열하는 것을 말한다.

 

순열과의 차이점은 바로 '순서'!!

조합은 순서를 가지지 않으므로 {1, 2, 3}, {3, 2, 1}을 같은 것으로 본다.

 

그리고 조합도 순열처럼 중복 조합이라는 개념이 존재하는데,

{1, 1, 1}, {1, 1, 2}, ... 처럼 중복을 허용한다. 하지만 이 때도 순서를 가지지 않는다는 점은 동일!

 

👉  정리하자면,

조합이 가지는 순열과의 차이점은 '순서'이다.

기본 조합은 순서를 가지며 중복을 허용하지 않고,

중복 조합은 순서를 가지며 중복을 허용한다.

---

📎 기본 조합 구현

public class Combination1 {
	
	static char[] src = { 'a', 'b', 'c', 'd' };
	
	/*
     * 기본 조합: 중복 X, 순서 X
     * @param nth - 몇 번째 선택인지 표현
     * @param choosed - 선택된 요소
     * @param startIdx - 몇 번째 요소부터 반복하며 선택할 것인지 표현
     */
    static void makeCombination(int nth, char[] choosed, int startIdx) {
        if(nth == choosed.length) { // 기저 조건: choosed를 다 채웠다면 끝
        	System.out.println(Arrays.toString(choosed));
        	return;
        }
        
        for(int i = startIdx; i < src.length; i++) {
        	choosed[nth] = src[i];
        	makeCombination(nth+1, choosed, i+1); // 중복 방지를 위한 장치: i+1
        }
    }

	public static void main(String[] args) {
        System.out.println("조합");
        makeCombination(0,new char[3], 0); // src에서 3개를 뽑아 만들 수 있는 조합을 모두 출력
	}

}

nth를 이용해서 조합의 몇 번째 요소를 선택했는지 표현했고,

choosed에 선택한 요소들을 차례대로 담아 조합을 완성시킬 수 있게 했다.

startIdx는 반복을 시작할 값을 담는데, 중복을 방지하기 위하여

현재 선택한 요소가 있다면 그 다음 값부터 선택할 수 있도록 했다.

---

📎 중복 조합 구현

public class Combination2 {
	
	static char[] src = { 'a', 'b', 'c', 'd' };
	
	/*
     * 중복 조합: 중복 O, 순서 X
     * 기본 조합에서 startIdx를 +1하는 것만 빼면 ok
     * 
     * @param nth - 몇 번째 선택인지 표현
     * @param choosed - 선택된 요소
     * @param startIdx - 몇 번째 요소부터 반복하며 선택할 것인지 표현
     */
    static void makeCombinationDup(int nth, char[] choosed, int startIdx) {
        if(nth == choosed.length) { // 기저 조건: choosed를 다 채웠다면 끝
        	System.out.println(Arrays.toString(choosed));
        	return;
        }
        
        for(int i = startIdx; i < src.length; i++) {
        	choosed[nth] = src[i];
        	makeCombinationDup(nth+1, choosed, i); // 중복 방지하지 않아도 되므로 i를 그대로 넘겨줌
        }
    }

	public static void main(String[] args) {
        System.out.println("조합");
        makeCombinationDup(0,new char[3], 0); // src에서 3개를 뽑아 만들 수 있는 조합을 모두 출력
	}

}

중복 조합은 기본 조합 구현과 거의 동일한데,

재귀 호출 시 startIdx 자리에 i+1이 아닌 그냥 i를 넣어준다는 점이 차이점이다.

현재 선택한 인덱스를 다음에 또 선택해도 되므로 이렇게 구현할 수 있다.

---

👀 정리

조합은 중복 없이 요소들을 뽑아 순서를 가지도록 나열한 것을 의미하고,

중복 조합은 중복을 허용하여 요소들을 뽑아 순서를 가지도록 나열한 것이다.

조합과 중복 조합은 순열과 마찬가지로 재귀를 이용하여 구현할 수 있는데,

중복 조합은 조합 구현 메서드에서 중복을 허용하지 않는 부분만 제거해주면 된다.