비트 마스크(Bit Mask) - 활용(순열)

 저번에는 비트마스크로 부분집합을 도출하는 것을 알아보았다.

 

이번에는 순열이다.

 

순열은 같은 숫자들을 뽑아도 뽑는 순서에 따라 해당 집합이 가지는 가치가 다르다는 걸 전제로 한다.

 

즉 1 2 와 2 1은 같은 숫자를 뽑았지만 뽑은 순서가 다르기 때문에 서로 다르다고 본다.

 

이를 비트마스크를 통해 구현해보자.

 

 

#include <iostream>
using namespace std;
int *arr;
int n;
int *result;


void cal(int idx, int v) {
	if (idx == n) {
		for (int i = 0; i < n; i++) {
			cout << result[i]<<" ";
		}
		cout << endl;
		return;
	}
	for (int i = 0; i < n; i++){
		if ((v&(1 << i)) != 0)continue;
		result[idx] = arr[i];
		cal(idx + 1, v | (1 << i));
		}
}

int main() {
	arr =new int [3] {0, 1, 2};
	n = 3;
	result = new int[n];
	cal(0, 0);
}

 

위의 코드의 결과는 다음과 같다.

 

 

같은 숫자를 뽑은 0 1 2와 2 0 1을 확인할 수 있다.

 

위의 코드는 부분집합과 달리 이전에 뽑은 것들을 순서에 따라 다시 뽑는 것을 허용한다.

 

여기서는 비트 연산을 해당 숫자를 뽑았는지 뽑지 않았는지 확인할 때 쓰게 된다.

 

idx는 몇개를 뽑았는지를 확인하는 파라미터로, 현재는 n개를 뽑는 걸로 조건을 걸어 두었다.

 

v는 가지고 있는 수 중 몇 번째 수를 뽑았는지를 확인할 때 사용한다.

 

수 집합 0 1 2 에서 

 

아무것도 뽑지 않은 상태에서 첫 번째를 뽑았다면 

 

i=0,

 

v&(1<<i) == 0일 것이다. 

 

따라서 이를 result 배열에 추가하고, v|(OR)(1<<i) 연산을 해준다.

 

즉 현재 v는 0 0 0이고, 1<<i 는 0 0 1 이기 때문에 

 

OR 연산으로 0 0 1이 된다. 

 

이는 1번째 요소를 뽑았다는 걸 의미한다.

 

이를 0부터 n-1까지 반복하니 이전에 뽑았던 수를 다시 집어넣었을 경우에도, 

 

즉, 0 1 2 에서 뽑았던 0을 2 0 1 에서 순서만 바뀌면 뽑을 수 있는 것이다.

 

간단한 예시로 비트마스크를 통한 순열을 알아보았다.

 

라고 이해했다.