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

Để 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 (x1, x2, …, xk) ởđây các xi∈ S và khác nhau đôi một.

Như vậy thủ tục Try(i) - xét tất cả các khả năng chọn xi - 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:

Khởi tạo một mảng c1, c2, …, cn mang kiểu logic. Ởđây ci 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.

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

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

Sau khi gọi đệ quy tìm xi+1: có nghĩa là sắp tới ta sẽ thử gán một giá trị khác cho xi thì ta sẽđặt giá trị j vừa thửđó thành tự do (cj := TRUE), bởi khi xi đã nhận một giá trị khác rồi thì các phần tử đứng sau: xi+1, xi+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: x1 có n cách chọn, x2 có n - 1 cách chọn, …Lưu ý rằng khi thủ tục Try(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 ≤ 20) 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, 2, …, n}

ARRANGE.INP 3 2 ARRANGE.OUT 1 2 1 3 2 1 2 3 3 1 3 2

Chuyên đề Đại học Sư phạm Hà Nội, 1999-2002 16 program Arrangement; const InputFile = 'ARRANGES.INP'; OutputFile = 'ARRANGES.OUT'; max = 20; 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 Try(i: Integer); {Thử các cách chọn xi}

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}

Try(i + 1); {Thủ tục này chỉ xét những giá trị còn tự do gán cho xi+1, tức là sẽ không chọn phải j} 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 xi}

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}

Try(1); {Thử các cách chọn giá trị của x1}

Close(f); end.

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