부분집합_재귀함수_조합 구하기 (JAVA)

[ 조합 (Combination) ]

• n개의 원소 중 r개의 원소를 꺼내는 경우의 수
• 순서가 유효하지 않기 때문에 중복을 허용하지 않음 (순열은 순서가 유효하므로 중복 허용)
• 경우의 수 : nPr / r! = n! / r! * (n-r)!
• 표기법 : nCr

순열과 달리 순서가 필요없어서 중복을 허용하지 않는 것을 조합이라고 합니다. {1,2,3}과 {3,2,1}은 같은 것으로 간주합니다. 예를 들어 {1,2,3} 중 2개를 곱해서 나올 수 있는 숫자를 구하라고 한다면 "{1,2} = 2", "{2,1} =2" 이기 때문에 순서에 상관 없이 원소의 종류만 맞으면 됩니다.

 

---

 

 

이전 글의 순열 코드를 약간 수정해 조합이 되었기 때문에 순열의 원리를 이해하면 금방 이해를 할 수 있습니다. 순열 코드는 백준 알고리즘에서 문제가 딱 있어서 검증을 했는데 사실 조합 코드는 갯수 구하는 문제밖에 없어서 정확히 검증을 하지는 못했습니다. 하지만 인터넷의 다른 코드들을 가져와서 수차례 결과를 비교해본 결과 동일한 것으로 확인했습니다. 하지만 혹시 예외 경우가 생길 수 있다는 점에 유의하셔야할 듯합니다. 혹시 문제있는거 같으면 댓글 부탁드립니다.

 

원리 자체는 순열과 동일하니 이전글을 보시면 더 이해하기 편리할 것 같습니다. 코드의 핵심은 "nPr에서 하나를 뽑고 다시 n-1Pr-1을 구하도록 재귀함수를 호출 시킨다"입니다. 기준이 되는 값은 반복문으로 순회시키고 계속해서 재귀함수를 호출시킵니다.

 

[JAVA/- 알고리즘 및 자료구조] - 부분집합_재귀함수_순열 구하기 (JAVA)

 

* 전체 코드

package pojoPrj;

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

class Main {

	public int result;

	public static void main(String[] args) {

		List<String> arr = new ArrayList<>();
		arr.add("1");
		arr.add("2");
		arr.add("3");

		List<String> result = new ArrayList<>();
		reculsion(arr, result, 0, arr.size(), 2);

	}

	/**
	 * 조합 구하기
	 * 
	 * @param arr    : 기준 리스트
	 * @param result : 결과를 담아줄 리스트
	 * @param index  : 반복문 시작 인덱스
	 * @param n      : 전체 갯수
	 * @param r      : 뽑을 갯수
	 */
	private static void reculsion(List<String> arr, List<String> result, int index, int n, int r) {

		if (r == 0) {

			System.out.println(result.toString());
			return;
		}

		for (int i = index; i < n; i++) {

			result.add(arr.get(i));
			reculsion(arr, result, i + 1, n, r - 1);
			result.remove(result.size() - 1);
		}
	}
}

 

 

---

 

순열에서는 자기 자신을 제외하고 모든 원소를 처음부터 검색해 조합해야했기 때문에 재귀함수를 이용하기 위해 원본 배열에서 해당 원소를 뺐다가 붙였다가를 반복했습니다. "c"가 제일 앞에 오는 경우 나머지 원소들의 부분집합을 처음부터 추가해줘야 하기 때문이죠.

 

 

 

 

하지만 조합에서는 "a"가 포함된 부분집합을 모두 구한 뒤에는 더 이상 "a"를 선택할 필요가 없습니다. "b"로 시작할 때는 이후 원소들에서만 뽑아오면 됩니다. 따라서 기준이 "b"라면 다음 재귀함수는 "b"다음 인덱스부터 시작하면 되기 때문에 원본 배열을 굳이 건드릴 이유가 없게 됩니다. 

 

 

 

 

---

 

 

따라서 아래와 같이 기존 순열 코드에서는 기준이 되는 인덱스 값을 만들어주는 반복문의 시작이 "i = 0" 이었지만 index라는 파라미터를 추가해서 현재 재귀함수를 호출한 인덱스보다 한 칸 뒤("i + 1")부터 다시 시작하게 만들어 주면 됩니다. 

 

* 순열 코드

	/**
	 * 순열 구하기
	 * 
	 * @param arr    : 기준 리스트
	 * @param result : 결과를 담아줄 리스트
	 * @param n      : 전체 갯수
	 * @param r      : 뽑을 갯수
	 */
	private static void reculsion(List<String> arr, List<String> result, int n, int r) {

		if (r == 0) {

			System.out.println(result.toString());
			return;
		}

		for (int i = 0; i < n; i++) {

			result.add(arr.remove(i));
			reculsion(arr, result, n - 1, r - 1);
			arr.add(i, result.remove(result.size() - 1));
		}
	}

 

 

* 조합 코드

	/**
	 * 조합 구하기
	 * 
	 * @param arr    : 기준 리스트
	 * @param result : 결과를 담아줄 리스트
	 * @param index  : 반복문 시작 인덱스
	 * @param n      : 전체 갯수
	 * @param r      : 뽑을 갯수
	 */
	private static void reculsion(List<String> arr, List<String> result, int index, int n, int r) {

		if (r == 0) {

			System.out.println(result.toString());
			return;
		}

		for (int i = index; i < n; i++) {

			result.add(arr.get(i));
			reculsion(arr, result, i + 1, n, r - 1);
			result.remove(result.size() - 1);
		}
	}