Thuật toán sinh kế tiếp – 3.Bài toán liệt kê các tập con m phần tử của tập n phần tử

Thuật toán sinh kế tiếp

Bài toán liệt kê các tập con m phần tử của tập n phần tử

Bài toán: Cho một tập hợp X = {1, 2, 3, …, n – 1,  n}. Hãy liệt kê tất cả các tập con m < n phần tử của X.

Xét bài toán ví dụ: Cho tập A = {1, 2, 3, 4, 5} , hãy liệt kê các tập con có 3 phần tử của A.

Ta sẽ liệt kê được các tập con như bảng sau. Hãy xem bảng và tìm quy luật của nó.

STT
1	1	2	3
2	1	2	4
3	1	2	5
4	1	3	4
5	1	3	5
6	1	4	5
7	2	3	4
8	2	3	5
9	2	4	3
10	3	4	5

*          Quy luật của dãy đó là:

– Tìm tử bên phải dãy a₁, a₂,  a₃, …, a_m phần tử a_i ≠ n  – m + i.

– Thay thế a_i = a_i + 1.

– Thay a_j  = a_i + j – i, với j = i + 1, i + 2, …, m.

*          Phân tích ví dụ: (Xét từ  a_{0 ,} …, a_m-1)

– Ở hàng thứ 1 -> 2 ta thấy a₂ (= 3) ≠  n  – m + i ( = 5 – 3 + 2 = 4).

Vì vậy thay thế a_i = a_i + 1 = 3 + 1 = 4.

-Tương tự ở hàng thứ 2 -> 3 cũng giống 1 -> 2.

– Ở hàng 3 -> 4, ta thấy ở a₂ (= 4) = n  – m + i ( = 5 – 3 + 2 = 4) vậy xét đến a₁ = 2 ) ≠  n  – m + i ( = 5 – 3 + 1 = 3). Vậy thay thế a₁  = a₁ + 1 = 3.

Vì bên phải a_i còn có các phần tử a_j khác với j = i + 1, i + 2, …, m. Ta thấy ở đây chỉ còn mỗi một phần tử  ứng với j  = 2, thay a_j  = a_i + j – i (= 3 + 2 – 1 = 4).

– Các hàng khác quy luật tương tự.

– Ta có số tập con được tạo ra là  5C3 = 10.

–>Cài  đặt chương trình ( sử dụng C ++)