[Algorithm] Thuật toán sinh tổ hợp lặp chập k của n phần tử
Tổ hợp lặp là gì ?
Chúng ta cần phân biệt giữa tổ hợp lặp với tổ hợp thông thường (tổ hợp không lặp).
Tổ hợp lặp: Mỗi cách chọn ra k vật từ n loại vật khác nhau (trong đó mỗi loại vật có thể được chọn lại nhiều lần) được gọi là tổ hợp lặp chập k của n . Số các tổ lặp chập k của n được ký hiệu là K(k,n) .
Công thức tính tổ hợp lặp: K(k,n) = C (k, n+k−1)
Với C là kí hiệu của tổ hợp không lặp.
Ví dụ: với k = 3 ; n= 2 : Ta có các tổ hợp lặp sau: (1,1,1) , (1,1,2) , (1,2,2) và (2,2,2).
Thuật toán sinh tổ hợp lặp:
Đầu tiên ta cần biết ý tưởng đề cài đặt một thuật toán sinh là gì. Để cài đặt thành công thuật toán sinh ta cần 2 yếu tố:
- Xác định được cấu hình đầu và cấu hình cuối.
- Xác định được quy luật để sinh một cấu hình từ cấu hình hiện tại.
Áp dụng trong bài toán này (k =3 và n =2 ) ta sẽ có:
Cấu hình đầu : (1,1,1) và cấu hình cuối (2,2,2)
Quy luật: lần lượt tăng giá trị của các số từ phải qua cho đến khi bằng n. Ví dụ: với cấu hình hiện tại là (1,1,1), tăng số tính từ bên phải ta sẽ có cấu hình tiếp theo là (1,1,2).
Chương trình mẫu bằng C++:
Chương trình mẫu in tất cả tổ hợp lặp chập k của n phần tử viết bằng C++ :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> using namespace std; int k , n ; int a[100000] ; void printResult() { for(int i =1 ; i <=k ; i++) { cout<<a[i]<<" " ; } cout<<endl ; } void sinh() { // sinh cấu hình đầu tiên for(int i =1 ; i <=k ; i++) { a[i] =1 ; } printResult() ; // sinh cau hình tiếp theo int j = k ; while(a[1]<n) { if(a[j]==n) { j-- ; } a[j]++ ; printResult() ; } } int main() { cin>>k>>n ; if(k<0 || n < 0 ) { cout<<"Loi: k,n >0"<<endl ; } else { sinh() ; } return 0; } |
Chương trình mẫu bằng Java:
Phía dưới là chương trình viết bằng Java. Do mình viết theo hướng đối tượng và đảm bảo “tính đóng gói” của nó nên viết hơi kĩ nhé để sau này có gì kế thừa hay tái sử dụng cho dễ. 🙂
Mô tả chương trình:
Để sử dụng được chương trình, ta cần khởi tạo đối tượng ToHopLap với 2 tham số k và n. Sau đó gọi hàm generate(). Kết quả sinh ra lưu vào danh sách kết quả là ResultList. (Xem cụ thể tại hàm main )
Lưu ý: mỗi phần tử của ResultList mình thiết kế thành kiểu String nhé.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
import java.util.ArrayList; import java.util.Scanner; public class ToHopLap { public int k; public int n; public ArrayList<String> ResultList; // mảng lưu trữ danh sách kết quả public ToHopLap(int k, int n) { this.k = k; this.n = n; ResultList = new ArrayList<>(); } int result[] = new int[1000000] ; // mảng cấu hình public void insert() { // chèn một cấu hình vào danh sách kết quả String temp = ""; for (int i = 1; i <= k; i++) { temp += result[i] + " "; } ResultList.add(temp); } public void generate() { // generate cấu hình đầu tiên for (int i = 1; i <= k; i++) { result[i] = 1 ; } insert(); // thêm cấu hình vào vào tập kết quả // generate cau hình tiếp theo int j = k; while (result[1] < n) { if (result[j]== n) { j--; } result[j]++ ; insert(); // thêm cấu hình vào vào tập kết quả } } public static void main(String[] args) { int k = 0, n = 0; Scanner s = new Scanner(System.in); k = s.nextInt(); n = s.nextInt(); ToHopLap thl = new ToHopLap(k, n); thl.generate(); // in kết quả for (String result : thl.ResultList) { System.out.println(result); } } } |
About Author
