LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K

Để liệt kê các chỉnh hợp không lặp chập k của tập S = {1, 2, …, n} ta có thể đưa về liệt kê các cấu hình x[1..k] ở đây các x[i] Î S và khác nhau đôi một.

Như vậy thủ tục Attempt(i) - xét tất cả các khả năng chọn x[i] - sẽ thử hết các giá trị từ 1 đến n, mà các giá trị này chưa bị các phần tử đứng trước chọn. Muốn xem các giá trị nào chưa được chọn ta sử dụng kỹ thuật dùng mảng đánh dấu:

v Khởi tạo một mảng c[1..n] mang kiểu logic boolean. Ở đây c[i] cho biết giá trị i có còn tự do hay đã bị chọn rồi. 

Ban đầu khởi tạo tất cả các phần tử mảng c là TRUE có nghĩa là các phần tử từ 1 đến n đều tự do.

v Tại bước chọn các giá trị có thể của x[i] ta chỉ xét những giá trị j có c[j] = TRUE có nghĩa là chỉ chọn những giá trị tự do.

v Trước khi gọi đệ quy tìm x[i+1]: ta đặt giá trị j vừa gán cho x[i] là đã bị chọn có nghĩa là đặt c[j] := FALSE để các thủ tục Attempt(i + 1), Attempt(i + 2)… gọi sau này không chọn phải giá trị j đó nữa

v Sau khi gọi đệ quy tìm x[i+1]: có nghĩa là sắp tới ta sẽ thử gán một giá trị khác cho x[i]  thì ta sẽ đặt giá trị j vừa thử đó thành tự do (c[j] := TRUE), bởi khi xi đã nhận một giá trị khác rồi thì các phần tử đứng sau: x[i+1], x[i+2] … hoàn toàn có thể nhận lại giá trị j đó. 

Điều này hoàn toàn hợp lý trong phép xây dựng chỉnh hợp không lặp: x[1] có n cách chọn, x[2] có n - 1 cách chọn, …Lưu ý rằng khi thủ tục Attempt(i) có i = k thì ta không cần phải đánh dấu gì cả vì tiếp theo chỉ có in kết quả chứ không cần phải chọn thêm phần tử nào nữa.

Input: file văn bản ARRANGE.INP chứa hai số nguyên dương n, k (1 £ k £ n £ 100) cách nhau ít nhất một dấu cách
Output: file văn bản ARRANGE.OUT ghi các chỉnh hợp không lặp chập k của tập {1, …, n}

ARRANGE.INP

3 2

ARRANGE.OUT

1 2

1 3

2 1

2 3

3 1

3 2

P_1_03_3.PAS * Thuật toán quay lui liệt kê các chỉnh hợp không lặp chập k

{$MODE DELPHI} (*This program uses 32-bit Integer [-231..231 - 1]*) program Arrangement_Enumeration;

const

InputFile = 'ARRANGES.INP';

OutputFile = 'ARRANGES.OUT'; max = 100;

var

x: array[1..max] of Integer; c: array[1..max] of Boolean; n, k: Integer;

f: Text;

procedure PrintResult; {Thủ tục in cấu hình tìm được}

var

i: Integer; begin

for i := 1 to k do Write(f, x[i], ' '); WriteLn(f);

end;

procedure Attempt(i: Integer); {Thử các cách chọn x[i]}

var

j: Integer; begin

for j := 1 to n do

if c[j] then {Chỉ xét những giá trị j còn tự do}

begin

x[i] := j;

if i = k then PrintResult {Nếu đã chọn được đến xk thì chỉ việc in kết quả}

else

begin

c[j] := False; {Đánh dấu: j đã bị chọn}

Attempt(i + 1); {Thủ tục này chỉ xét những giá trị còn tự do gán cho x[i+1]}

c[j] := True; {Bỏ đánh dấu: j lại là tự do, bởi sắp tới sẽ thử một cách chọn khác của x[i]}

end;

end;

end;

begin

Assign(f, InputFile); Reset(f);

ReadLn(f, n, k);

Assign(f, OutputFile); Rewrite(f);

FillChar(c, SizeOf(c), True); {Tất cả các số đều chưa bị chọn}

Attempt(1); {Thử các cách chọn giá trị của x[1]}

Close(f); end.

Nhận xét: khi k = n thì đây là chương trình liệt kê hoán vị