부분집합 열거 비트트릭

p.434의 KAKURO2 문제를 풀려고 보니 많은 스킬이 필요하여 따로 정리하였다.

부분집합 열거 패턴#

1) 어떤 집합을 비트마스크 s로 표현할 때, s의 모든 부분집합 sub를 도는 반복문#

for(int sub=s; ; sub=(sub-1)&s) {
	printf("0x%08X\n", sub);
	if(sub==0) break;
}

2) 핵심 원리#

아래의 식이 핵심이다.

sub = (sub-1) & s

sub-1 은 가장 오른쪽 1을 0으로 만들고, 바뀐 숫자의 모든 오른쪽을 1로 채운다. 그래서 & s 를 하게 되면 s안에 있는 원소만 남기면서 가능한 한 큰 수를 만들 수 있다.

사실 이렇게만 얘기하면 어느 정도 이해는 가지만 이게 중복 없이 모든 부분집합을 순회한다는 게 잘 안와닿는데, sub-1 은 sub보다 반드시 작아지면서 정수단위로 가장 작게 감소하는 식이고, 여기서 & s를 적용하여 s의 부분집합 공간으로 다시 투영하므로, (sub-1) & s로 얻어지는 값은 sub보다 작으면서 s의 부분집합중 가장 큰 값을 의미하게 된다. 또한 해당 식이 반복문을 통해 연쇄적으로 적용되므로, sub가 s부터 시작해서 0으로 끝날 때까지 sub = (sub-1) & s 식을 적용하게 되면, s의 모든 부분집합을 순회할 수 있게 된다.