Chương trình C ++ để tạo tất cả các tập con của một tập hợp đã cho theo thứ tự đồ họa Lexico

Đây là chương trình C ++ để tạo tất cả các tập con của một tập hợp cho trước theo thứ tự đồ họa Lexico. Thuật toán này in tất cả các kết hợp có thể có của mỗi độ dài từ tập hợp mảng đã cho theo thứ tự tăng dần. Độ phức tạp về thời gian của thuật toán này là O (n * (2 ^ n)).

Thuật toá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

Ví dụ

#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;
}

Đầu ra

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 }