aaaabbbccd 를 나열 할 때 서로 다른 순서쌍의 개수를 구하는 문제는 확률과 통계라는 과목에서 많이 다루었던 문제이다.
그 개수는 10!/(4!*3!*2!*1!) 이렇게 구했던 거로 기억한다.
이번에는 이러한 순서쌍이 실제로 어떻게 생성되는지 코드로 구현해 볼 차례이다.
내가 구현한 코드의 알고리즘은 다음과 같다.
111 22 3 이 있다 했을 때,
먼저 1은 총 3개가 있다. 그래서 1의 자리를 먼저 배치한다.
[1][][][][][], - 1c
[1][1][][][][], - 2c
[1][1][1][][][], - 3c
여기서 중요한 부분은 1c에서 2c로 넘어 갔을 때 해당 1은 1c에서 선택된 자리 다음부터 선택 할 수 있다는 것이다.
이를 통해 111 이 중복되는 것을 막을 수 있다.
예를 들어 아래에 경우에는
[][1][][][][], - 1c
[1][1][][][][], - 2c
[1][1][1][][][], - 3c
위의 경우와 중복이 됨 을 볼 수 있다.
그래서 "1", 3개를 다 쓰고 나면 더 이상 쓸 수 없기 때문에 2를 나열 하게 되는데, 2는 1과는 다른 것이기 때문에 첫번째 부터 배치 할 수 있다.
결국 이러한 실행을 재귀로 구현하였다.
char op[4] = { '+', '-', '*', '/' };
int eq[4] = { 2, 1, 1, 1 }; // +, -, *, /
int sel[5] = { -1, -1, -1, -1, -1};
int ret = 0;
static void same_per(int idx, int st)
{
if (idx == 4)
{
printf("%c %c %c %c %c\n", op[sel[0]], op[sel[1]], op[sel[2]], op[sel[3]], op[sel[4]]);
ret += 1;
return;
}
if (!eq[idx])
same_per(idx + 1, 0);
else
{
eq[idx] -= 1;
for (int s = st; s < 5; s++)
{
if (sel[s] < 0)
{
sel[s] = idx;
same_per(idx, s + 1);
sel[s] = -1;
}
}
eq[idx] += 1;
}
}위 코드는 ++-*/ 를 나열하는 경우를 찾는 것을 모델링하여 코딩한 것이다.
eq의 각 인덱스는 순서대로 +, - ,*, / 를 의미하게 된다.
sel은 해당 위치에 올 문자의 인덱스를 저장한다. 0이 +라는 것을 의미하기 때문에 -1인 경우에는 해당 위치가 아직 선택되지 않았기 때문에 선택하게 되고 재귀 호출 한 뒤, 해당 자리를 반납하는 것이다.
제일 먼저 호출 할 때에는 same_per(0, 0); 으로 호출 하면 되는데, eq의 첫번째 부터 시작하며, 해당 문자는 첫번째 자리 부터 선택 할 수 있다는 것을 의미한다.
