이 글에서는 특정 경우에 대한 정수 분할(Integer Partition)을 수행하는 C++ 프로그램을 다룹니다. 양의 정수 n이 주어졌을 때, n을 양의 정수들의 합으로 나타낼 수 있는 모든 고유한(unique) 방법을 생성하는 것이 목표입니다. 예를 들어 n = 7이라면 7, 6+1, 5+2, 5+1+1처럼 순서만 다른 중복 표현을 제외한 모든 조합을 출력하게 됩니다.
알고리즘
Begin
function displayAllUniqueParts(int m):
1) 파티션에서 마지막 원소의 인덱스 k를 0으로 설정한다.
2) 첫 번째 파티션을 숫자 자기 자신으로 초기화한다. 즉, p[k] = m
3) 현재 파티션을 먼저 출력한 뒤 다음 파티션을 생성하는 while 루프를 만든다.
이 루프는 현재 파티션의 모든 값이 1이 될 때 종료된다.
4) displayArray(p, k + 1) 함수로 현재 파티션을 출력한다.
5) 다음 파티션을 생성한다.
6) val = 0으로 초기화한다.
p[] 배열에서 가장 오른쪽에 있는 1이 아닌 값을 찾는다.
동시에 val을 갱신하여 추가로 수용 가능한 값의 크기를 파악한다.
만약 k < 0이라면,
모든 값이 1이므로 더 이상 만들 수 있는 파티션이 없다.
위에서 찾은 p[k]를 감소시키고 val을 조정한다.
7) val이 더 크다면 내림차순 정렬 순서가 깨진 것이므로,
val을 p[k] 크기의 여러 값으로 나누어 p[k] 뒤의 서로 다른 위치에 복사한다.
val을 다음 위치에 복사하고 위치를 하나 증가시킨다.
End예제 코드
#include<iostream>
using namespace std;
void displayArray(int p[], int m) { // 배열을 출력하는 함수
for (int i = 0; i < m; i++)
cout << p[i] << " ";
cout << endl;
}
void displayAllUniqueParts(int m) {
int p[m];
int k = 0;
p[k] = m;
while (true) {
displayArray(p, k + 1);
int val = 0; // val 초기화
while (k >= 0 && p[k] == 1) {
val += p[k]; // val 갱신
k--;
}
if (k < 0)
return;
p[k]--;
val++;
// val이 더 큰 경우
while (val > p[k]) {
p[k + 1] = p[k];
val = val - p[k];
k++;
}
p[k + 1] = val;
k++;
}
}
int main() {
cout << "Display All Unique Partitions of integer:7\n";
displayAllUniqueParts(7);
return 0;
}실행 결과
Display All Unique Partitions of integer:7 7 6 1 5 2 5 1 1 4 3 4 2 1 4 1 1 1 3 3 1 3 2 2 3 2 1 1 3 1 1 1 1 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1
동작 원리
이 알고리즘은 각 파티션을 내림차순 배열로 관리하면서 사전순과 유사한 순서로 다음 파티션을 생성합니다. 매 단계에서 배열의 가장 오른쪽에 있는 1이 아닌 값을 하나 줄이고, 줄인 만큼 남은 값(val)을 규칙에 맞게 뒤쪽에 재배치합니다. 예를 들어 4 2 1 다음에는 4 1 1 1이, 그다음에는 3 3 1이 차례로 만들어집니다. 결국 모든 값이 1로만 이루어진 마지막 파티션(n개의 1)에 도달하면 탐색이 종료되며, 이 과정에서 중복 없이 모든 고유한 분할 결과를 빠짐없이 얻을 수 있습니다.