직순열을 출력하려면 ‘이미 출력한 숫자들의 정보’를 알아야한다. 그런데 문제는 ‘순열’이라면 조합과는 다르게 순서가 다르면 다른 종류라는 것이다.

이런저런 생각을 해보면 위와같은 정보를 담기 위해서는 boolean 배열을 넘기는 것이 좋아보이기는 하지만 ‘배열’은 포인터로 넘어가기 때문에 경우에따라 다르게 사용하려면 깊은 복사를 해야하고, 그러면 그만큼 오래걸린다. 10!만해도 3628800가지가 나오기 때문이다.
그래서 떠올린 것은 액세스도 빠르고 표시하는 것도 빠르도록 비트연산을 이용하는 것이다.

32비트 정수 int를 이용하면 대략 31!까지 표시가 가능하다. 그런데 31!은 8*10^33이므로 여기까지 구할수는 없으므로, int만 사용해도 충분할 듯 하다.(사실 16비트까지만해도 상관은 없을 것 같다.)

그러기 위해 매크로함수 몇개를 정의해보자.

[code language=”cpp”]
#define GET_FLAG(p, x) ((p) >> (x) & 0x1) // x-1자리의 비트를 가져온다.
#define SET_FLAG(p, x) ((p) | (1 << (x))) // x-1자리의 비트를 1로 설정한다.
#define GET_MAXFLAG(x) ((1 << (x)) – 1) // 0~x-1까지 1로 차있는 수를 가져온다.
[/code]

이미 출력한 수는 비트 1로, 아니면 0으로 표기한다고 하자.

예를 들어 1~4까지 나열하는 순열을 출력할 때, 1을 출력했다고 하면 플래그는 0000 0000 0000 0000 0000 0000 0000 0001이 된다.
1을 이미 출력했으므로 다음 턴에는 플래그 0000 0000 0000 0000 0000 0000 0000 0001를 가지고 ‘비트가 1인 자리인 1을 제외한’ 숫자를 ‘하나씩 따로 출력’하고 다음 것을 출력해야한다.
1) 2를 출력했을때 플래그는 … 0011 가 되고, 다음에 3이나 4를 출력한다.
2) 3을 출력했을때 플래그는 … 0101 이 되고, 다음에 2나 4를 출력한다
3) 4를 출력했을때 플래그는 … 1001 이 되고, 다음에 2나 3을 출력한다.

이러한 부분은 루프와 재귀호출을 이용하면 될 듯 싶다.

[code language=”cpp”]
#include<iostream>
#include<string>
#include<sstream>
using namespace std;

void perm(int size, string s = "", int flag = 0){
// 플래그 비트가 다 찼으면 출력하고 끝낸다.
if(GET_MAXFLAG(size) == flag){
cout << s << endl;
return;
}

stringstream ss;
for(int i = 0; i < size; i++){
// 플래그 비트가 1이면 출력하지 않는다.
if(!GET_FLAG(flag, i)){
ss << s << ‘ ‘ << (i+1);
// 출력한 비트를 표시하고 이어서 출력한다
perm(size, ss.str(), SET_FLAG(flag, i));
ss.str(""); // 스트림을 비운다.
}
}
}
[/code]

그러하다.
테스트해본 결과 31!까지는 무난히 출력하는 듯 하다 (….) 물론 31!을 끝까지 본건 아니고..