C++로 합집합이 전체 집합이 되는 모든 부분집합 쌍 생성하기

개요

이 글에서는 C++를 이용해, 두 부분집합의 합집합이 원래의 집합(전체 집합)과 같아지는 모든 부분집합 쌍을 생성하는 방법을 소개합니다.

핵심 아이디어는 각 원소에 이진 코드의 비트 값을 대응시키는 것입니다. 비트가 '1'이면 첫 번째 부분집합에, '0'이면 두 번째 부분집합에 해당 원소를 배치합니다. n개의 원소가 있을 때 중복되지 않는 쌍의 개수는 2^(n-1)개이며, 이진 코드를 0부터 2^(n-1)-1까지 순회하면 모든 경우를 빠짐없이 만들어 낼 수 있습니다.

알고리즘

시작
    함수 UnionSet():
    매개변수:
        a[] = 원소를 담고 있는 배열
        n   = 원소의 개수
    함수 본문:
        1) 2^(n-1)개의 모든 쌍을 위해 0부터 2^(n-1)-1까지의 이진 코드를 생성한다.
        2) 각 코드에 대해, 코드 문자열에서 해당 인덱스의 값이 '1'인 원소는 첫 번째 집합에,
           '0'인 원소는 두 번째 집합에 배치하여 출력한다.
        3) 이렇게 출력된 두 집합의 합집합은 항상 전체 집합(상위 집합)이 된다.
끝

예제 코드

#include<iostream>
#include<math.h>
using namespace std;

// 이진 코드를 기준으로 두 부분집합 쌍을 출력하는 함수
void display(char code[], int a[], int n) {
    int i;
    cout << "\t{ ";
    for(i = 0; i < n; i++) {
        if(code[i] == '1')      // 비트가 1이면 첫 번째 집합에 포함
            cout << a[i] << " ";
    }
    cout << "}";
    cout << " { ";
    for(i = 0; i < n; i++) {
        if(code[i] == '0')      // 비트가 0이면 두 번째 집합에 포함
            cout << a[i] << " ";
    }
    cout << "}\n";
}

void UnionSet(int a[], int n) {
    int i, r, l;
    char binary[n];             // 각 원소의 소속을 나타내는 이진 코드
    r = pow(2, n-1);            // 생성해야 할 쌍의 개수: 2^(n-1)
    for(i = 0; i < n; i++)
        binary[i] = '0';        // 이진 코드를 000...0으로 초기화
    for(i = 0; i < r; i++) {
        display(binary, a, n);  // 현재 코드에 해당하는 쌍 출력
        l = n - 1;
h:                              // 이진 코드를 1씩 증가 (2진수 덧셈)
        if(binary[l] == '0')
            binary[l] = '1';
        else {
            binary[l] = '0';
            l--;
            goto h;
        }
    }
}

int main() {
    int i, n;
    cout << "\n원소의 개수를 입력하세요: ";
    cin >> n;
    int a[n];
    cout << "\n";
    for(i = 0; i < n; i++) {
        cout << i + 1 << "번째 원소 입력: ";
        cin >> a[i];
    }
    cout << "\n합집합 시 전체 집합이 되는 부분집합 쌍:\n";
    UnionSet(a, n);
    return 0;
}

실행 결과

원소의 개수를 입력하세요: 4
1번째 원소 입력: 4
2번째 원소 입력: 3
3번째 원소 입력: 2
4번째 원소 입력: 1

합집합 시 전체 집합이 되는 부분집합 쌍:
{ } { 4 3 2 1 }
{ 1 } { 4 3 2 }
{ 2 } { 4 3 1 }
{ 2 1 } { 4 3 }
{ 3 } { 4 2 1 }
{ 3 1 } { 4 2 }
{ 3 2 } { 4 1 }
{ 3 2 1 } { 4 }

코드 설명

display() 함수

display() 함수는 현재 이진 코드 문자열을 받아 두 부분집합을 화면에 출력합니다. 코드에서 값이 '1'인 위치의 원소들은 왼쪽 집합에, '0'인 위치의 원소들은 오른쪽 집합에 나열됩니다.

UnionSet() 함수

UnionSet() 함수는 길이가 n인 문자형 배열 binary를 하나의 이진 카운터처럼 사용합니다. 처음에는 모든 비트를 '0'으로 초기화한 뒤, 쌍을 한 번 출력할 때마다 이진수 덧셈 방식으로 코드를 1씩 증가시킵니다. 루프는 총 2^(n-1)번 반복되므로 {A, B}와 {B, A}처럼 순서만 다른 중복 쌍 없이 모든 조합을 정확히 한 번씩 출력할 수 있습니다.

실행 결과를 보면 공집합과 전체 집합의 쌍부터 시작해, 한쪽에 원소가 하나만 있는 쌍, 두 개의 원소를 가진 쌍까지 모두 포함되며, 각 쌍의 합집합은 항상 {1, 2, 3, 4}가 됩니다.

참고 사항

위 예제는 설명의 편의를 위해 가변 길이 배열(VLA)을 사용했습니다. VLA는 표준 C++ 사양이 아니므로 실제 프로젝트에서는 std::vector나 동적 할당을 사용하는 것이 안전합니다. 또한 pow() 함수는 부동소수점 연산을 수행하므로, 정확한 정수 연산이 필요하다면 (1 << (n-1))과 같은 비트 시프트 연산으로 대체하는 것이 좋습니다.