[C/C++] 프로젝트 오일러 #106 Special Subset Sums: Meta-testing(점화식)

Project Euler #106: Special Subset Sums: Meta-testing 문제는 주어진 집합에서 두 개의 부분집합을 비교할 때, 그 부분집합들이 특정 조건을 만족하는지를 검사하는 경우의 수를 구하는 문제입니다.

문제를 간단히 설명하면,
1. 집합: 크기 n 인 자연수 집합 \(  \{1, 2, 3, \dots, n\} \)가 주어진다.
2. 부분집합 조건: 두 부분집합 A 와 B 가 다음 조건을 만족하는지 확인해야 한다:
• \(  |A| = |B| \) (부분집합의 크기가 동일해야 한다.)
• A와 B가 서로 다른 부분집합이어야 한다.
• A와 B의 합을 비교하는 것이 의미 있으려면, A와 B를 “비교 가능한 형태”로 만들어야 한다.
• “비교 가능”하다는 것은, 두 부분집합이 항목의 순서에 따라 항상 합을 비교할 수 없는 경우를 포함하는 상황이다. 이를 위해 추가적인 검사가 필요합니다.

문제의 핵심은 특정 n에 대해, 위 조건을 만족하는 모든 검사가 필요한 경우의 수를 계산하는 것입니다.
이 문제는 조합론적인 사고와 알고리즘적인 최적화가 필요하며, 집합의 성질과 대칭성, 그리고 계산 복잡성을 이해하는 것이 중요합니다.

 

set and combination

 

제가 문제를 풀기위해서 작성한 코드입니다.

//------------------------------------------------
//    Project Euler #106 - Special Subset Sums: Meta-testing
//        - by Aubrey Choi
//        - created at 2015-04-13
//------------------------------------------------
#include <stdio.h>

//    total cases.
//    f(1) = 0, f(2) = 1, f(3) = 6, f(4) = 25, f(7) = 966
//    f(n) = 2f(n-1) + 2^{n-1}
//    f(n) = \sum_{1 <= s <= n/2} comb(n, s)comb(n-s, s)/2
//         + \sum_{1 <= s < t and s+t <= n} comb(n, s)comb(n-s, t)

//    n = 3's non ordered sets. (all 5)
//    ooxxxo
//    oxoxxo
//    oxxoox
//    oxxoxo
//    oxxxoo

int comb(int n, int r)
{
    int s = 1;
    if( n-r < r ) r = n-r;
    for( int i = 1 ; i <= r ; i++ ) s*=n--, s/=i;
    return s;
}

int testcount(int set[], int n, int d)
{
    if( d == n )
    {
        int setb[100];
        int k = 0;
        int t = 1;
        for( int i = 1 ; i < n ; i++ )
        {
            while( t < set[i] ) setb[k++] = t++;
            t = set[i]+1;
        }
        while( k < n ) setb[k++] = t++;
        int i, j;
        int ordered = 0;
        for( i = 0 ; i < n ; i++ )
        {
            for( j = 0 ; j < n ; j++ ) if( set[i] < setb[j] ) break;
            if( j < n ) { ordered++; setb[j] = 0; }
        }
        if( ordered < n )
        {
            for( int i = 0 ; i < n ; i++ ) printf("%d ", setb[i]);
            char t[] = "xxxxxxxxxxxxxxxxxxxxxx";
            for( int i = 0 ; i < n ; i++ ) t[set[i]] = 'o';
            printf("%.*s\n", n*2, t);
        }
        return ordered < n;
    }
    int count = 0;
    for( int i = set[d-1]+1 ; i < 2*n ; i++ )
    {
        set[d] = i;
        count += testcount(set, n, d+1);
    }
    return count;
}

int getminimaltest(int n)
{
    int set[100];
    set[0] = 0;
    return testcount(set, n, 1);
}

int main()
{
    int minimal[7];
    for( int s = 2 ; s <= 6 ; s++ ) minimal[s] = getminimaltest(s);
    for( int n = 2 ; n <= 12 ; n++ )
    {
        int c = 0;
        for( int s = 1 ; s <= n/2 ; s++ ) c += (comb(n, s)*comb(n-s, s))/2;
        for( int s = 1 ; s <= n/2 ; s++ )
        {
            for( int t = s+1 ; s+t <= n ; t++ )
            {
                c += comb(n, s)*comb(n-s, t);
            }
        }
        int d = 0;
        for( int s = 2 ; s <= n/2 ; s++ ) d += comb(n, 2*s)*minimal[s];
        printf("%d : %d (%d)\n", n, c, d);
    }
}

 

이 코드는 조합론 및 재귀를 활용하여 Project Euler #106 문제를 해결합니다. 핵심적으로 두 가지 아이디어를 사용합니다:
1. 조합을 활용한 경우의 수 계산
• 조합(combination)을 사용하여 n개의 원소에서 서로 다른 부분집합의 경우의 수를 계산합니다.
• \(  \text{comb}(n, r) \): n개의 원소 중 r개를 선택하는 경우의 수를 계산합니다.
2. 재귀적 탐색
• 가능한 모든 부분집합 쌍을 재귀적으로 탐색하며, 조건에 따라 필요한 비교 여부를 판별합니다.
• 재귀를 통해 A와 B 두 부분집합의 순서를 조합적으로 생성하고, 조건을 확인합니다.

1. comb 함수

int comb(int n, int r)

• 조합 계산 함수입니다.
• \(  \binom{n}{r} \) 을 효율적으로 계산하기 위해 팩토리얼을 사용하지 않고, 곱셈과 나눗셈으로 계산합니다.

2. testcount 함수

int testcount(int set[], int n, int d)

• 재귀적으로 가능한 부분집합 A와 B를 생성합니다.
• set 배열을 이용하여 현재 탐색 중인 부분집합의 인덱스를 저장합니다.
• A와 B가 “순서 비교가 필요한 경우”인지 판별하고, 조건에 부합하면 카운트를 증가시킵니다.
• setb 배열은 A에 포함되지 않은 나머지 원소로 구성된 B 부분집합입니다.
• 출력 디버깅 코드도 포함되어 있어, 어떤 부분집합이 비교 대상인지 확인 가능합니다.

3. getminimaltest 함수

int getminimaltest(int n)

• 특정 n에 대해 필요한 비교 테스트의 최소 개수를 계산합니다.
• n개의 원소를 이용해 testcount를 호출합니다.

4. main 함수
• minimal 배열은 크기 n에 대한 최소 비교 테스트 개수를 저장합니다.
• 두 가지 방법으로 비교 가능한 부분집합 쌍의 총 개수를 계산합니다:
\[  \sum_{1 \leq s \leq n/2} \binom{n}{s} \cdot \binom{n-s}{s} / 2 \]
\[  \sum_{1 \leq s < t, s + t \leq n} \binom{n}{s} \cdot \binom{n-s}{t} \]
• 결과를 출력하며, 총 필요한 비교 수와 최소 비교 수를 각각 계산해 출력합니다.