Liệt kê tổ hợp

HD:

Để liệt kê các tập con k phần tử của tập S = {1,2,…,n} ta có thể đưa về liệt kê các cấu hình x[1…n], ở đây các x[i] thuộc S và x[1] < x[2] < … < x[m].

Ta có nhận xét như sau:

 

x[m] <= n

x[m-1] <= x[m]-1 <= n-1

x[i] <= n-m+i

x[1] <= n-m+1

Khi đó khả năng của x[i] là từ x[i-1]+1 đến n-m+i (x[0]=0)

  • Chấp nhận khả năng j: luôn chấp nhận
  • Xác định x[i] theo j: x[i]=j
  • Ghi nhận 1 đáp số: Xuất dãy x[i]

Code tham khảo liệt kê tổ hợp chặp:

 

Share
Share