C++로 집합을 k개의 부분 집합으로 나누는 방법의 수 구하기

문제 소개

두 개의 숫자 e(원소의 개수)와 p(파티션의 수)가 주어졌을 때, 집합의 e개 원소를 p개의 파티션(부분 집합)으로 나눌 수 있는 모든 경우의 수를 구하는 것이 목표입니다.

예제

입력

e=4 p=2

출력

Count of number of ways to partition a set into k subsets are: 7

설명

원소가 a, b, c, d일 때 이를 2개의 파티션으로 나누는 방법은 다음과 같습니다.

(a,b,c)-(d), (a,b)-(c,d), (a,b,d)-(c), (a)-(b,c,d), (a,c)-(b,d), (a,c,d)-(b), (a,d)-(b,c)

총 7가지 방법이 있습니다.

입력

e=2 p=2

출력

Count of number of ways to partition a set into k subsets are: 1

설명

원소가 a, b일 때 이를 2개의 파티션으로 나누는 방법은 (a)-(b) 한 가지뿐입니다.

접근 방식: 동적 계획법(Dynamic Programming)

이 문제는 재귀 관계를 활용한 동적 계획법으로 효율적으로 해결할 수 있습니다. e개의 원소를 p개의 파티션으로 나누는 경우는 다음 두 가지 상황으로 나누어 생각할 수 있습니다.

현재 원소가 기존 파티션 중 하나에 들어가는 경우: e−1개의 원소를 p개의 파티션으로 나누는 방법이 ways(e−1, p)가지 있다면, 현재 원소는 이 p개의 파티션 어디에든 들어갈 수 있으므로 p × ways(e−1, p)가지 방법이 됩니다.
현재 원소가 새로운 파티션을 만드는 경우: e−1개의 원소를 p−1개의 파티션으로 나누는 방법이 ways(e−1, p−1)가지 있다면, 현재 원소가 단독으로 새 파티션을 구성하므로 1 × ways(e−1, p−1)가지 방법이 추가됩니다.

따라서 최종 점화식은 다음과 같습니다.

ways(e, p) = p × ways(e−1, p) + ways(e−1, p−1)

단순 재귀 호출로 구현하면 동일한 하위 문제가 여러 번 반복 계산되어 비효율적입니다. 이러한 중복 계산을 피하기 위해 계산 결과를 테이블에 저장하는 동적 계획법을 사용합니다. 참고로 이 값은 조합론에서 제2종 스털링 수(Stirling number of the second kind) S(e, p)와 같습니다.

알고리즘

원소의 개수(elements)와 파티션의 수(partition)를 입력받습니다.
함수 partition_k(int elements, int partition)는 두 값을 인자로 받아 집합을 k개의 부분 집합으로 나누는 방법의 수를 반환합니다.
ways(e, p)의 값을 저장하기 위해 2차원 배열 arr[elements + 1][partition + 1]을 선언합니다.
i = 0부터 i = elements까지 반복하며 arr[i][0] = 0으로 설정합니다. 파티션 수가 0이면 나누는 방법도 없기 때문입니다(ways(i, 0) = 0).
j = 0부터 j = partition까지 반복하며 arr[0][j] = 0으로 설정합니다. 원소가 0개면 역시 방법이 없기 때문입니다(ways(0, j) = 0).
i = 1부터 i ≤ elements까지, j = 1부터 j ≤ i까지 이중 반복문으로 배열의 나머지 값을 채웁니다.
원소 수와 파티션 수가 같으면(i == j), 또는 파티션이 하나뿐이면(j == 1) 방법은 항상 1가지이므로 arr[i][j] = 1로 설정합니다.
그 외의 경우에는 temp_1 = arr[i−1][j−1], temp_2 = arr[i−1][j]로 저장하고, 점화식에 따라 arr[i][j] = j * temp_2 + temp_1로 갱신합니다.
모든 반복이 끝나면 arr[elements][partition]에 전체 방법의 수가 저장됩니다.
arr[elements][partition]을 결과로 반환합니다.

C++ 코드 예제

#include <iostream>
using namespace std;

int partition_k(int elements, int partition){
    int arr[elements + 1][partition + 1];

    // 파티션 수가 0이면 방법의 수는 0
    for(int i = 0; i <= elements; i++){
        arr[i][0] = 0;
    }

    // 원소 수가 0이면 방법의 수는 0
    for(int j = 0; j <= partition; j++){
        arr[0][j] = 0;
    }

    for(int i = 1; i <= elements; i++){
        for (int j = 1; j <= i; j++){
            if (j == 1 || i == j){
                arr[i][j] = 1;
            } else {
                int temp_1 = arr[i-1][j-1];
                int temp_2 = arr[i-1][j];
                arr[i][j] = j * temp_2 + temp_1;
            }
        }
    }
    return arr[elements][partition];
}

int main(){
    int elements = 4;
    int partition = 2;
    cout<<"Count of number of ways to partition a set into k subsets are: "<<partition_k(elements, partition);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Count of number of ways to partition a set into k subsets are: 7

마무리

이 알고리즘은 시간 복잡도 O(e × p), 공간 복잡도 O(e × p)로 동작하며, 재귀적 정의를 테이블에 누적 계산함으로써 지수적인 중복 연산을 제거합니다. e와 p 값이 커져도 안정적으로 결과를 얻을 수 있다는 점이 동적 계획법 적용의 핵심 장점입니다.