개요
이 프로그램은 주어진 집합의 모든 부분집합을 사전식 순서(lexicographic order)로 생성하여 출력하는 C++ 코드입니다. 배열에 담긴 원소들로부터 만들 수 있는 각 길이별 조합을 오름차순으로 정렬해 모두 출력하며, 알고리즘의 시간 복잡도는 O(n × 2ⁿ)입니다.
n개의 원소를 가진 집합의 부분집합 개수는 공집합을 포함해 총 2ⁿ개입니다. 예를 들어 원소가 6개라면 공집합을 포함해 총 64개의 부분집합이 생성됩니다.
알고리즘
각 길이 i(1부터 n까지)에 대해 GenAllSubset() 함수를 호출하는 방식으로 동작합니다.
시작
각 길이 'i'마다 GenAllSubset() 함수를 호출한다:
1) GenAllSubset() 내부에서 currLen이 reqLen보다 크면 함수를 종료(return)한다.
2) currLen이 reqLen과 같으면 새로운 부분집합이 완성된 것이므로 이를 출력한다.
3) start를 'true'로 설정하고, currLen과 s를 1씩 증가시킨 상태로
GenAllSubset()을 재귀 호출한다.
그렇지 않으면
start를 'false'로 설정하고, s만 1 증가시킨 상태로
GenAllSubset()을 재귀 호출한다.
끝동작 원리
핵심 아이디어는 bool 타입의 check 배열을 사용해 각 원소를 현재 부분집합에 포함할지(true) 제외할지(false)를 결정하는 것입니다. 재귀 호출을 통해 두 가지 경우를 모두 탐색하며, 선택된 원소의 개수(currLen)가 요구한 길이(reqLen)에 도달하면 해당 조합을 출력합니다.
먼저 Sorting() 함수로 배열을 오름차순으로 정렬한 뒤 부분집합을 생성하기 때문에, 결과가 자연스럽게 사전식 순서로 출력됩니다.
예제 코드
#include<iostream>
using namespace std;
void Sorting(int a[], int n) //배열 정렬 {
int i, j, t;
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
if(a[i] > a[j]) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
}
void GenAllSubset(int a[], int reqLen, int s, int currLen, bool check[], int len) {
if(currLen > reqLen)
return;
else if (currLen == reqLen) {
cout<<"\t";
cout<<"{ ";
for (int i = 0; i < len; i++) {
if (check[i] == true) {
cout<<a[i]<<" ";
}
}
cout<<"}\n";
return;
}
if (s == len) {
return;
}
check[s] = true;
GenAllSubset(a, reqLen, s + 1, currLen + 1, check, len);
check[s] = false;
GenAllSubset(a, reqLen, s + 1, currLen, check, len);
}
int main() {
int i, n;
bool ch[n];
cout<<"Enter the number of element array have: ";
cin>>n;
int arr[n];
cout<<"\n";
for (i = 0; i < n; i++) {
cout<<"Enter "<<i+1<<" element: ";
cin>>arr[i];
ch[i] = false;
}
Sorting(arr, n);
cout<<"\nThe all subset of the given set in the lexicographic order: \n";
cout<<"\t{ }\n";
for(i = 1; i <= n; i++) {
GenAllSubset(arr, i, 0, 0, ch, n);
}
return 0;
}실행 결과
원소 6개(3, 2, 1, 7, 6, 5)를 입력했을 때의 출력 결과입니다. 먼저 배열이 {1, 2, 3, 5, 6, 7}로 정렬되고, 길이가 0인 공집합부터 길이가 6인 전체 집합까지 모든 부분집합이 사전식 순서로 출력됩니다.
Enter the number of element array have: 6
Enter 1 element:3
Enter 2 element: 2
Enter 3 element: 1
Enter 4 element:7
Enter 5 element:6
Enter 6 element: 5
The all subset of the given set in the lexicographic order:
{ }
{ 1 }
{ 2 }
{ 3 }
{ 5 }
{ 6 }
{ 7 }
{ 1 2 }
{ 1 3 }
{ 1 5 }
{ 1 6 }
{ 1 7 }
{ 2 3 }
{ 2 5 }
{ 2 6 }
{ 2 7 }
{ 3 5 }
{ 3 6 }
{ 3 7 }
{ 5 6 }
{ 5 7 }
{ 6 7 }
{ 1 2 3 }
{ 1 2 5 }
{ 1 2 6 }
{ 1 2 7 }
{ 1 3 5 }
{ 1 3 6 }
{ 1 3 7 }
{ 1 5 6 }
{ 1 5 7 }
{ 1 6 7 }
{ 2 3 5 }
{ 2 3 6 }
{ 2 3 7 }
{ 2 5 6 }
{ 2 5 7 }
{ 2 6 7 }
{ 3 5 6 }
{ 3 5 7 }
{ 3 6 7 }
{ 5 6 7 }
{ 1 2 3 5 }
{ 1 2 3 6 }
{ 1 2 3 7 }
{ 1 2 5 6 }
{ 1 2 5 7 }
{ 1 2 6 7 }
{ 1 3 5 6 }
{ 1 3 5 7 }
{ 1 3 6 7 }
{ 1 5 6 7 }
{ 2 3 5 6 }
{ 2 3 5 7 }
{ 2 3 6 7 }
{ 2 5 6 7 }
{ 3 5 6 7 }
{ 1 2 3 5 6 }
{ 1 2 3 5 7 }
{ 1 2 3 6 7 }
{ 1 2 5 6 7 }
{ 1 3 5 6 7 }
{ 2 3 5 6 7 }
{ 1 2 3 5 6 7 }