Home » Lập trình » [Algorithm] Thuật toán quay lui liệt kê tổ hợp chập k của n phần tử

[Algorithm] Thuật toán quay lui liệt kê tổ hợp chập k của n phần tử

backstracking

Tổ hợp là gì ?

Tổ hợp chập k các phần tử của A (0\le k \le n) là một tâp con k phần tử (0<=k<=n) của tập A.

Ví dụ: với  k = 3 , n =4, ta có các tổ hợp sau: (1,2,3) (1,2,4) (1,3,4) , (1,2,4).

Trong toán học, công tính số tổ hợp là :

cong thuc to hop

 

Tuy nhiên, trong bài viết này chúng ta cần liệt kê tất cả các cấu hình chứ không phải đi tính số tổ hợp có thể có. 🙂

Thuật toán quay lui:

Ý tưởng cơ bản của thuật toán quay lui là lần lượt xét hết các trạng thái có thể có. Cụ thể, trong ví dụ trên (k=3 , n=4) ta có một cấu hình tổ hợp cần liệt kê có dạng  (a[1],a[2],a[3]) trong đó, a[i] có thể là 1,2,3 hoặc 4.

Dạng tổng quát của thuật toán quay lui như sau:

Nhận xét: Hai yếu tố quyết định thời gian thực hiện của thuật toán là :

  • Xác định danh sách “các khả năng của x[i]” sao cho ít khả năng nhất.
  • Xác định điều kiện “chấp nhận khả năng j”: điều kiện này cần đơn giản nhất nếu có thể.

Vậy để xây dựng được thuật toán quay lui ta cần biết:

  • Dạng của cấu hình cần tìm.
  • Tất cả các khả năng của x[i].
  • Điều kiện chấp nhận khả năng j.

Thuật toán quay lui liệt kê tổ hợp:

Áp dụng mô hình của thuật toán quay lui trên vào bài toán liệt kê các tổ hợp chập k của n phần tử.

Lần lượt xét yếu tố cơ bản của thuật toán quay lui trong bài toán sinh tổ hợp:

  • Dạng của cấu hình cần tìm: Đáp số có thể biểu diễn dạng (x1, x2, …,xn), với xi-1<xi.
  • Tất cả các khả năng của x[i]: Giá trị của xi là từ x[i-1]+1 cho đến n-k+i ( Cấu khởi tạo x[0]=1). Ví dụ: với k =3 và n =4 , thì có các miền giá trị:

x[1]=1,2;

 x[2]=x[1]+1,..,3;

x[3]3=x[2]+1,..,4

  • Điều kiện “chấp nhận khả năng j” : Để sinh tổ hợp, ta không cần xét điều kiện chấp nhận j.

Chương trình C++ quay lui để liệt kê tổ hợp :

 

 

Share
  • Wind

    for(int j = a[i-1]+1 ; j<=-k+i ; j++ )
    có chút sai sót nhỏ ở đây

    • Vani

      Cảm ơn bạn Wind nhé, phải sửa thành :
      for(int j = a[i-1]+1 ; j< =n-k+i ; j++ )

Share
Free WordPress Themes - Download High-quality Templates