นี่คือโปรแกรม C++ สำหรับสร้างเซตย่อย (Subsets) ทั้งหมดที่มีสมาชิก k ตัวในแต่ละเซต
อัลกอริทึม
เริ่มต้น ฟังก์ชัน PossibleSubSet(char a[], int reqLen, int s, int currLen, bool check[], int l): ถ้า currLen > reqLen คืนค่า มิฉะนั้น ถ้า currLen = reqLen พิมพ์ลำดับที่สร้างขึ้นใหม่ ถ้า s = l คืนค่า ไม่มีองค์ประกอบเหลือ สำหรับทุกดัชนี มี 2 ทางเลือก: ไปต่อกับ start เป็น 'true' และเรียก PossibleSubSet() แบบเรียกซ้ำ พร้อมเพิ่มค่า 'currLen' และ 's' หรือไปต่อกับ start เป็น 'false' และเรียก PossibleSubSet() แบบเรียกซ้ำ พร้อมเพิ่มค่า 's' เท่านั้น จบ
ตัวอย่างโค้ด
#include<iostream> using namespace std; void PossibleSubSet(char a[], int reqLen, int s, int currLen, bool check[], int l) //พิมพ์ทุกชุดการจัดหมู่ของชุดอาร์เรย์ที่กำหนด { if(currLen > reqLen) return; else if (currLen == reqLen) { cout<<"\t"; for (int i = 0; i < l; i++) { if (check[i] == true) { cout<<a[i]<<" "; } } cout<<"\n"; return; } if (s == l) { return; } check[s] = true; PossibleSubSet(a, reqLen, s + 1, currLen + 1, check, l); //เรียก PossibleSubSet() แบบเรียกซ้ำพร้อมเพิ่มค่า 'currLen' และ 's' check[s] = false; PossibleSubSet(a, reqLen, s + 1, currLen, check, l); //เรียก PossibleSubSet() แบบเรียกซ้ำพร้อมเพิ่มค่า 's' เท่านั้น } int main() { int i,n,m; bool check[n]; cout<<"Enter the number of elements: "; cin>>n; char a[n]; cout<<"\n"; for(i = 0; i < n; i++) { cout<<"Enter "<<i+1<<" element: "; cin>>a[i]; check[i] = false; } cout<<"\nEnter the length of the subsets required: "; cin>>m; cout<<"\nThe possible combination of length "<<m<<" for the given array set:\n"; PossibleSubSet(a, m, 0, 0, check, n); return 0; }
ผลลัพธ์
Enter the number of elements: 7 Enter 1 element: 7 Enter 2 element: 6 Enter 3 element: 5 Enter 4 element: 4 Enter 5 element: 3 Enter 6 element: 2 Enter 7 element: 1 Enter the length of the subsets required: 6 The possible combination of length 6 for the given array set: 7 6 5 4 3 2 7 6 5 4 3 1 7 6 5 4 2 1 7 6 5 3 2 1 7 6 4 3 2 1 7 5 4 3 2 1 6 5 4 3 2 1
