[Thuật Toán] Sinh các chỉnh hợp lặp chập k của n

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 !