Power Set theo thứ tự Lexicographic trong C ++

Trong bài toán này, chúng ta được cung cấp chuỗi str. Nhiệm vụ của chúng tôi là in tập hợp lũy thừa của các phần tử của chuỗi này theo thứ tự từ vựng.

Bộ nguồn - Tập hợp lũy thừa của một tập hợp là tập hợp tất cả các tập hợp con của tập hợp. Được ký hiệu bởi P (S) trong đó s là tập hợp.

Ví dụ -

S = {1, 2, 3} ;
p(S) = {{}, {1}, {1, 2}, {1, 3}, {2}, {2, 3}, {3}, {1,2,3}}

Trong bài toán này, chúng ta sẽ coi chuỗi như một tập hợp. Vì vậy, các ký tự của nó sẽ là các phần tử của tập hợp.

Hãy lấy một ví dụ để hiểu vấn đề

Đầu vào - str =“xyz”

Đầu ra - x xy xyz xz y yz z

Để giải quyết vấn đề này, chúng ta sẽ phải sắp xếp mảng để có được thứ tự từ vựng. Sau đó, chúng tôi sẽ sửa một phần tử của chuỗi và gọi đệ quy cho các phần tử còn lại sẽ tạo ra tất cả chuỗi con. Và loại bỏ phần tử cố định đầu tiên để có được hoán vị tiếp theo.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#include <bits/stdc++.h>
using namespace std;
void printAllSubsets(string str, int n, int index = -1, string subset = "") {
   if (index == n)
      return;
   cout<<subset<<"\n";
   for (int i = index + 1; i < n; i++) {
      subset+= str[i];
      printAllSubsets(str, n, i, subset);
      subset = subset.erase(subset.size() - 1);
   }
   return;
}
void GeneratePowerSet(string str) {
   sort(str.begin(), str.end());
   printAllSubsets(str, str.size());
}
int main() {
   string str = "xyz";
   cout<<"Power Set of the string '"<<str<<"' is :\n";
   GeneratePowerSet(str);
   return 0;
}

Đầu ra

Power Set of the string 'xyz' is:
x xy xyz xz y yz z