[ETC] JAVA -조합, 중복조합 구현 - 공룡 루디

 조합

알고리즘 문제풀이를 하다 보면 조합을 구해야 하는 경우가 많습니다.

 

대표적으로 BruteForce 문제 같은 경우, 여러 가지 경우를 시도해야 하는데 이때

조합, 중복조합, 순열, 중복순열, 부분집합 등이 쓰일 때가 많습니다.

 

Python이나 C++ 같은 경우 라이브러리가 제공되지만

JAVA 같은 경우 내부 라이브러리에서 조합과 순열 등을 제공하지 않고

구글? 에서 제공하는 라이브러리를 이용하면 된다고 들었습니다.

 

하지만!

구현이 그렇게 어려운 것도 아니고

라이브러리에 의존하지 않는 게 좋다고 들어서

배우고 공부한 내용을 토대로 구현을

해보았습니다.

 

import java.util.Arrays;

public class Combination {
	
	static int [] selected;
	static int count;
	static void makeCombination(int[] arr, int R, int cnt, int start) {
		
		if(cnt==R) {
			count++;
			System.out.println(Arrays.toString(selected));
		}else {
			for(int i=start;i<arr.length;i++) {
				selected[cnt]=arr[i];
				makeCombination(arr, R, cnt+1, i+1); //i+1이 핵심
			}
		}
	}
	
	public static void main(String[] args) {
		int [] arr = {1,2,3,4,5};
		int R = 3;
		selected = new int[R]; 			//selected는 선택된 원소가 들어갈 배열이므로 R개이다.
		
		//배열에 속한 N개의 원소들 중 R개를 뽑아 조합을 만들자
		//순열과 다르게 isSelected배열과 비트마스크가 필요 없지만 start변수가 필요함
		makeCombination(arr,R,0,0); // arr R cnt start
		System.out.println("조합의 개수: "+count);
	}
}

 

 

 중복 조합

 

중복 조합은

중복을 허용한 조합으로 중복순열에서 순서를 제거한 집합이라고 생각하시면 됩니다.

 

중복 조합을 구현하는 방법은

조합을 구현하는 방법에서 정말 살짝만 바꾸면 됩니다.

 

조합에서는 중복을 허용하지 않기 위해 start라는 변수를 파라미터로 다시 넣어줄 때

i+1을 했지만 

중복 조합은 중복을 허용하기 때문에 start라는 변수를 파라미터로 넣어줄 때

i값을 넣어주면 됩니다.

 

import java.util.Arrays;

public class CombinationWithRepetition {
	static int[] selected;
	static int count;

	static void makeCombination(int[] arr, int R, int cnt, int start) {

		if (cnt == R) {
			count++;
			System.out.println(Arrays.toString(selected));
		} else {
			for (int i = start; i < arr.length; i++) {
				selected[cnt] = arr[i];
				makeCombination(arr, R, cnt + 1, i);//중복 조합은 i+1이 아니고 그냥 i임!!
			}
		}
	}

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5 };
		int R = 3;
		selected = new int[R]; // selected는 선택된 원소가 들어갈 배열이므로 R개이다.

		// 배열에 속한 N개의 원소들 중 R개를 뽑아 조합을 만들자
		// 순열과 다르게 isSelected배열과 비트마스크가 필요 없지만 start변수가 필요함
		makeCombination(arr, R, 0, 0); // arr R cnt start
		System.out.println("중복 조합의 개수: " + count);
	}
}