Home » Lập trình » [Algorithm] Thuật toán sinh tổ hợp lặp chập k của n phần tử

[Algorithm] Thuật toán sinh tổ hợp lặp chập k của n phần tử

Generate-Algorithm

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++ :

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é.

 

 

Share
  • Lê Quốc Trung

    Bị thiếu mất vài trường hợp rồi bạn.

Share
Free WordPress Themes - Download High-quality Templates