[알고리즘/Java] 바이너리 카운팅을 이용한 부분집합 구하기

부분집합이란?

집합에 포함된 원소들을 순서 없이 선택하는 것.

집합의 원소가 N개일 때, 공집합을 포함한 부분집합의 수는 2^N개

각 원소를 부분집합에 포함시키거나 포함시키지 않는 두가지 경우를 모든 원소에 적용한 경우의 수와 같다.

 

일단 일반적인 재귀방법으로 부분집합을 작성하는 코드이다.

static void generateSubSet(int cnt) {
	if(cnt == N){
		for(int i = 0; i < N; i++) {
			if(isSelected[i]) {System.out.print(input[i] + "\t");}
		}
		return;
	}

	isSelected[cnt] = true;
	generateSubset(cnt + 1);
	isSelected[cnt] = false;
	generateSubset(cnt + 1);
}

 

예를 들어 현재 input에 {1, 2, 3, 4}라는 값이 들어있고 generateSubSet(0)이 호출되었다고 가정해본다.

isSelected[0] = true가 되므로 처음원소인 1이 선택된 채로 generateSubSet(1)이 호출된다.

이와 같은 과정을 반복해 cnt가 4가 된다면 모든 원소가 선택되어 1 2 3 4 가 출력된다. 여기서 이제 다시 호출되었던 곳으로 돌아간다면

isSelected[3] = false가 되어 원소 4는 선택되지 않은 경우의 수를 확인할 수 있게 된다.

그렇게 1 2 3과 같은 결과가 출력되게 되는 것이다.

 

바이너리 카운팅

원소의 개수 N개 만큼의 비트열을 사용해 부분집합을 구하는 방법이다.

n번째 비트값이 1이면 n번째 원소가 포함되었음을 의미한다.

{1, 2, 3, 4}라는 집합의 부분집합을 구하려면 비트열4개를 사용해서 구해야하고 다음과 같은 결과를 만들 수 있게 된다.

 

이를 코드로 구현하면?

private static void generateSubSet(int n) {
	for(int i = 0; i < (1 << n); i++) {
		for(int j = 0; j < n; j++) {
			if((i & 1 << j) != 0) {
				System.out.print(numbers[j] + "\t");
			}
		}
		System.out.println();
	}
}

 

1 << n :은 부분집합의 개수이다. i가 증가함에 따라 2진수로 바꾸면 위 표처럼 선택된 수가 바뀌게 된다.

j는 각 자리의 원소를 비교하기 위한 반복문으로 원소 수만큼 비교를 하게 된다.

i가 5이고 j가 2인 경우라고 생각해보자 그렇다면 if문의 i &  1 << j는 위 그림과 같은 연산을 하게된다.

그렇다면 0100 즉 3이 위치한 원소를 선택했다는 뜻이 되므로 3을 출력하게 되는 것이다.