부분 집합

부분 집합

• 집합에 포함된 원소들을 선택하는 것이다.
• N개 원소로 이루어진 집합에서 nC1, nC2, nC3, nC4, … , nCn-1, nCn ⇒ power set
• 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것이다.
  • ex) 배낭 짐싸기(knapsack)

부분 집합의 수

• 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개 이다.
• 이는 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.
• {1, 2, 3, 4} = > 2 2 2 * 2 = 16가지
• 2^10 = 약 1,000, 2^20 = 약 1,000,000, 2^30 = 약 1,000,000,000

반복문 부분 집합

**
 * subset의 개수는 2의 n승 개이므로 
 * 0 : 원소를 선택 안함    1:원소를 선택함      
 * 
 * 0      0000:  원소 하나도 선택안한 서브셋
 * 1      0001:  맨 끝의 원소 하나를 선택한 서브셋
 * 2      0010:  맨 끝에서 두번째 원소 하나를 선택한 서브셋   
 * 3      0011:  맨 끝의 두개의 원소를 선택한 서브셋 
 * ...
 * size-1 1111 : 모든 원소를 선택한 서브셋    
 * 
 * 시간 복잡도 2^n
 */

for (int i = 0; i < 2; i++) {
	subset[0] = i;
	for (int j = 0; j < 2; j++) {
		subset[1] = j;
		for (int k = 0; k < 2; k++) {
			subset[2] = k;
			for (int l = 0; l < 2; l++) {
				subset[3] = l;
				print(subset);
			}
		}
	}
}
static void print(int[] subset) {
	int k =0;
	System.out.print("[");
	for (int s : subset) {
		if(s!=0) {
			System.out.print(input[k]+" ");
		}
		k++;
	}
	System.out.println("]");
}

재귀 부분 집합 1

• 기저 조건에 도달했을 때, 추가적으로 N번만큼 isSelected를 탐색해야한다.

private static void generateSubset(int depth) {
	// N depth에 도달하면 isSelected가 true인 index를 원래의 집합에서 선택한다.
	if(depth == N) {
		totalCnt++;
		for (int i = 0; i < N; i++) {
			System.out.print((isSelected[i]?input[i]:"X")+"\t");
		}
		System.out.println();
		return ;
	}
	// 부분집합에 현재 원소를 선택
	isSelected[depth] = true;
	generateSubset(depth+1);
	
	// 부분집합에 현재 원소를 비선택
	isSelected[depth] = false;
	generateSubset(depth+1);
	}

재귀 부분 집합 2

• 개인적으로 가장 활용도가 높은 코드라고 생각한다.
• 새로운 배열에 부분 집합을 담았기 때문에 기존의 집합을 해치지 않는다.

/**
 *  부분집합 
 *  시간 복잡도  2^N
 *  
 *  24 powerset : 40ms 정도   안전
 *  25 powerset : 80ms 정도   약간 불안
 * 
 */

/**
 * 
 * @param depth	N의 원소 중 depth번째의 원소를 선택/비선택 하기 위한 index
 * @param len	선택한 원소를 numbers 배열에 저장하기 위한 index이면서 부분집합의 원소 개수
 */
private static void generateSubset(int depth, int len) {
	// N depth에 도달하면 isSelected가 true인 index를 원래의 집합에서 선택한다.
	if(depth == N) {
			totalCnt++;
//			System.out.println(Arrays.toString(Arrays.copyOfRange(numbers, 0, len)));
		return ;
	}
	// 부분집합에 현재 원소를 선택
	numbers[len] = input[depth];
	generateSubset(depth+1, len+1);
		
	// 부분집합에 현재 원소를 비선택
	generateSubset(depth+1, len);
}

비트 마스킹 부분 집합

• 2의 N승 만큼 반복하면서 각각 해당 원소가 부분 집합에 포함 되었는지 N번 만큼 반복하며 확인한다.
• 결과적으로 2의 N+1승 만큼 반복하기 때문에 비효율적이다.

/**
* subset의 개수는 2^n 개이다
* 0: 원소를 선택 안함,    1:원소를 선택함
* 
* 0		000	: 원소를 하나도 선택 안한 서브셋
* 1    	001 : 맨 끝번째에 있는 원소 하나를 선택한  서브셋 
* 2    	010 : 맨 끝에서 두번째에 있는 원소 하나를 선택한  서브셋
* 3    	011 : 맨 끝에 두개의 원소를 선택한 서브셋
* ...
* size-1	111 : 모든 원소를 선택한 서브
*	 
* 결국 0~2^n-1 까지 수의 bit를 1은 선택 0비선택으로 하면 
* 수 자체가 부분 집합을 표현한다. 
* 수에서 bit 값이 1인지를 확인해서 부분집합으로 표현할 수 있다. 
* 
* 시간 복잡도 2^n * n  ==> 2^(n+1)
*  
*/
for (int i = 0, end = 1<<N; i <end; i++) { //0부터 2의 N승 ==> i는 부분집합
	int len = 0;
	for (int j = 0; j <N; j++) {
		if((i & 1<<j) !=0) {		//j번째 위치한 bit가 1이면 선택한 원소
			numbers[len++] = input[j];
		}
	}
//	System.out.println(Arrays.toString(Arrays.copyOfRange(numbers, 0, len)));
}