THUẬT TOÁN SINH CÁC CHỈNH HỢP LẶP CHẬP K CỦA N
Xét về bản chất thì thuật toán sinh các chuỗi nhị phân
có độ dài là k thực chất là liệt kê các chỉnh hợp lặp chập k của 2 (vì tập nguồn
của chúng ta có 2 phần tử là 0 và 1).
Vậy thì nếu tập nguồn của chúng ta không
phải là 2 phần tử nữa, mà là n phần tử thì sao ?
Khi đó, bài toán mới của chúng ta sẽ là :
Cho tập X có n phần tử {1,2,…,n}. hãy liệt kê các chỉnh
hợp lặp chập k của n.
Ví dụ : với n = 2 và k = 3 nhập từ bàn phím thì các cấu hình của bài
toán là :
(111) ; (112) ; (121) ; (122) ; (211) ; (212) ; (221) ;
(222).
Theo công thức của chỉnh hợp lặp thì số các cấu hình = n^k= 2^3 = 8.
Và nhìn vào ví dụ trên, chúng ta cũng sẽ thấy cấu hình đầu là
toàn số 1 và cấu hình cuối toàn số n. và
ta dễ dàng tìm ra thuật toán như sau :
Xét từ cuối dãy về đầu, gặp chữ số có giá trị chưa bằng n :
· * Tăng chữ số đó lên 1 đơn vị
· * Gán tất cả phần tử sau vị trí đó = 1.
Thuật toán dừng lại khi sinh được cấu hình cuối gồm các
phần tử có giá trị đều = n.
Source code tham khảo :
#include<iostream> using namespace std; int n, k, a[10]; bool check = false; void display(){ for (int i = 1; i <= k; i++){ cout << a[i]; } cout << endl; } void nextString(){ int i = k; while (a[i]==n&&i>0){ // nếu a[i] = n và i > 0 thì giảm i i--; } if (i == 0) check = true; // nếu i = 0 thì đã đến cấu hình cuối cùng else { a[i]++; // tăng a[i] lên 1 đơn vị for (int j = i + 1; j <= k; j++){ a[j] = 1; // đặt tất cả phần tử phía sau a[i] = 1 } } } void main(){ cout << " nhap n = "; cin >> n; cout << " nhap k = "; cin >> k; for (int i = 1; i <= k; i++){ a[i] = 1; } while (!check){ display(); nextString(); } system("pause"); }bài viết chắc chắn còn nhiều thiếu sót rất mong bạn đọc góp ý qua email : trieuhiepptit@gmail.com Thanks for reading !
