โปรแกรม C++ สร้างทุกเซตย่อยของเซตที่กำหนดตามลำดับ Lexicographic

นี่คือโปรแกรม C++ สร้างทุกเซตย่อย (subsets) ของเซตที่กำหนดตามลำดับ Lexicographic อัลกอริทึมพิมพ์การจัดหมู่ที่เป็นไปได้ทุกความยาวจากอาเรย์ที่กำหนดในลำดับเพิ่มขึ้น ความซับซ้อนด้านเวลา O(n * 2^n)

อัลกอริทึม

Begin
  สำหรับแต่ละความยาว 'i' เรียก GenAllSubset():
    1) ใน GenAllSubset() ถ้า currLen มากกว่า reqLen คืนค่า
    2) มิฉะนั้น ถ้า currLen เท่ากับ reqLen จะมี sequence ใหม่สร้างขึ้น พิมพ์มัน
    3) ถ้าดำเนินต่อด้วย start เป็น 'true' เรียก GenAllSubset() ซ้ำด้วย currLen และ 's' เพิ่มขึ้น
       มิฉะนั้น
       ดำเนินต่อด้วย start เป็น 'false' เรียก GenAllSubset() ซ้ำด้วย 's' เพิ่มขึ้น
End

ตัวอย่างโค้ด

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

ผลลัพธ์

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 }