사전 그래픽 순서로 주어진 집합의 모든 부분 집합을 생성하는 C++ 프로그램

이것은 사전 그래픽 순서로 주어진 집합의 모든 부분 집합을 생성하는 C++ 프로그램입니다. 이 알고리즘은 주어진 배열 집합에서 각 길이의 가능한 모든 조합을 오름차순으로 인쇄합니다. 이 알고리즘의 시간 복잡도는 O(n*(2^n))입니다.

알고리즘

Begin
   For each length ‘i’ GenAllSubset() function is called:
   1) In GenAllSubset(), if currLen is more than the reqLen then return.
   2) Otherwise, if currLen is equal to reqLen then there will be a new sequence generated, print it.
   3) If proceed with a start as ‘true’ and recursively call GenAllSubset() with incremented value of ‘currLen’ and ‘s’.
   else
      proceed with a start as ‘false’ and recursively call GenAllSubset() with incremented value of ‘s’.
End

예시

#include<iostream>
using namespace std;
void Sorting(int a[], int n) //array sorting {
   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;
}

출력

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 }