LIỆT KÊ CÁC TẬP CON K PHẦN TỬ

Input/Output có khuôn dạng như trong P_1_02_2.PAS

 
Để 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] Î S và x[1] < x[2] < … < x[k]. 

Ta có nhận xét:
x[k] £ n
x[k-1] £ x[k] - 1 £ n - 1
…
x[i] £ n - k + i
…
x[1] £ n - k + 1.

Từ đó suy ra x[i-1] + 1 £ x[i] £ n - k + i (1 £ i £ k) ở đây ta giả thiết có thêm một số x[0] = 0 khi xét i = 1.

Như vậy ta sẽ xét tất cả các cách chọn x[1] từ 1 (=x[0] + 1) đến n - k + 1, với mỗi giá trị đó, xét tiếp tất cả các cách chọn x[2] từ x[1] +1 đến n - k + 2, … cứ như vậy khi chọn được đến x[k] thì ta có một cấu hình cần liệt kê. 

Chương trình liệt kê bằng thuật toán quay lui như sau:
 

P_1_03_2.PAS * Thuật toán quay lui liệt kê các tập con k phần tử

{$MODE DELPHI} (*This program uses 32-bit Integer [-2³¹..2³¹ - 1]*) program Combination_Enumeration;
const
InputFile = 'SUBSET.INP'; OutputFile = 'SUBSET.OUT'; max = 100;
var
x: array[0..max] of Integer; n, k: Integer;
f: Text;
 
procedure PrintResult;   (*In ra tập con {x[1], x[2], …, x[k]}*)
var
i: Integer; begin
Write(f, '{');
for i := 1 to k - 1 do Write(f, x[i], ', ');
WriteLn(f, x[k], '}'); end;
 
procedure Attempt(i: Integer); {Thử các cách chọn giá trị cho x[i]}
var
j: Integer; begin
for j := x[i - 1] + 1 to n - k + i do begin
x[i] := j;
if i = k then PrintResult else Attempt(i + 1);
end;
end;
 
begin
Assign(f, InputFile); Reset(F);
ReadLn(f, n, k);
Close(f);
Assign(f, OutputFile); Rewrite(f);

 
x[0] := 0;
Attempt(1);
Close(f);
end.

Nếu để ý chương trình trên và chương trình liệt kê dãy nhị phân độ dài n, ta thấy về cơ bản chúng chỉ khác nhau ở thủ tục Attemp(i) - chọn thử các giá trị cho x[i], ở chương trình liệt kê dãy nhị phân ta thử chọn các giá trị 0 hoặc 1 còn ở chương trình liệt kê các tập con k phần tử ta thử chọn x[i] là một trong các giá trị nguyên từ x[i-1] + 1 đến n - k + i. 

Qua đó ta có thể thấy tính phổ dụng của thuật toán quay lui: mô hình cài đặt có thể thích hợp cho nhiều bài toán, khác với phương pháp sinh tuần tự, với mỗi bài toán lại phải có một thuật toán sinh kế tiếp riêng làm cho việc cài đặt mỗi bài một khác, bên cạnh đó, không phải thuật toán sinh kế tiếp nào cũng dễ cài đặt.