Tập lũy thừa theo thứ tự từ điển trong C++

Trong bài toán này, ta được cho một chuỗi str. Nhiệm vụ là in ra tập lũy thừa (power set) của các phần tử chuỗi theo thứ tự từ điển (lexicographical order).

Tập lũy thừa (Power Set) – Tập lũy thừa của một tập là tập hợp tất cả các tập con của tập đó. Ký hiệu P(S) với S là tập ban đầu.

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, ta coi chuỗi như một tập hợp. Vì vậy, các ký tự của chuỗi sẽ là các phần tử của tập hợp.

Hãy xem ví dụ sau:

Đầu vào – str = "xyz"

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

Để giải bài toán, ta phải sắp xếp chuỗi để có thứ tự từ điển. Sau đó cố định một ký tự và gọi đệ quy cho các ký tự còn lại để sinh tất cả các xâu con. Sau đó loại bỏ ký tự cố định đầu tiên để lấy hoán vị tiếp theo.

Ví dụ minh họa

Chương trình triển khai giải pháp:

#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<<"Tập lũy thừa của chuỗi '"<<str<<"' là:\n";    GeneratePowerSet(str);    return 0; }

Kết quả

Tập lũy thừa của chuỗi 'xyz' là: x xy xyz xz y yz z