Tổ hợp

Liệt kê các tổ hợp chặp K của N  phần tử 1..N theo thứ tự từ điển tăng dần.

TOHOP.INP	TOHOP.OUT
5 3	1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

Dữ liệu vào: tệp văn bản TOHOP.INP

Dòng đầu tiên: hai số N và K cách nhau qua dấu cách,
1 £ N £ 9, K £ N.

Dữ liệu ra: tệp văn bản TOHOP.OUT

Mỗi dòng một tổ hợp, các số trên cùng dòng cách nhau qua dấu cách.

Thuật toán

Phương án 1. Ta khởi trị cho mảng x[1..K] là tổ hợp nhỏ nhất (1,2,…,K). Sau đó ta dùng hàm Next để sinh ra tổ hợp sát sau của x. Hàm Next hoạt động theo 2 pha như sau:

Pha 1. Dỡ. Duyệt ngược từ K qua trái bỏ qua những phần tử mang giá trị …N-2, N-1, N đứng cuối mảng. Nếu sau khi dỡ x không còn phần tử nào thì kết thúc với Next = false với ý nghĩa là sát sau tổ hợp x không còn tổ hợp nào. Thí dụ, nếu N = 7, K = 5, x[1..5] = (2,3,5,6,7) thì sau khi dỡ ba phần tử cuối của x ta thu được i = 2, x[1..2] = (2,3). Điều này cho biết sẽ còn tổ hợp sát sau.

Pha 2. Xếp.

2.1. Tăng phần tử x[i] thêm 1 đơn vị. Tiếp tục với thí dụ trên ta thu được x[1..2] = (2,4)

2.2. Xếp tiếp vào x cho đủ K phần tử theo trật tự tăng dần liên tục. Tiếp tục với thí dụ trên ta thu được x[1..5] = (2,4,5,6,7).

Ta sử dụng phần tử x[0] = N làm lính canh.

(* Pascal, Phuong an 1 *)

function Next: Boolean;

   var i, j, b: integer;

 begin

   Next := false; x[0] := N;

   { Pha 1. Do }

   i :=  k; b := n - k;

   while (x[i] = b + i) do i := i - 1;

   if (i = 0) then exit;

   { Pha 2. Xep }

   x[i] := x[i] + 1;

   for j := i + 1 to k do x[j] := x[j-1] + 1;

   Next := true;

 end;

Độ phức tạp: cho hàm Next: 2N, cho cả bài: 2N.C_N^K = (2N. N!) / (K! (N-K)!) .

Phương án 2.           Ta cải tiến hàm Next như sau. Giả sử sau pha 1 ta thu được vị trí i thỏa x[i] ≠ n-k+i. Ta gọi vị  trí này là vị trí cập nhật và sẽ điều khiển nó thông qua một biến v.  Ta khởi trị cho x và v như sau

 for i := 1 to k do x[i] := i;

      if (x[k] = n) then v := 0 else v := k;

Sau đó mỗi lần gọi hàm Next ta kiểm tra

Nếu v = 0 thì dừng hàm Next.

Nếu v ≠ 0 ta thực hiện pha 2 sau đó chỉnh lại giá trị của v như sau:

Nếu x[k] = n thì tức là x[v..k] = (n-k-v, ..., n-1, n) thì lần gọi Next tiếp theo sẽ cập nhật tại vị trí v-1, ngược lại, nếu x[k] ≠ n thì lần gọi Next tiếp theo sẽ cập nhật tại vị trí k.  

Độ phức tạp: cho hàm Next: N. Cho cả bài: N.C_N^K = (N. N!) / (K! (N-K)!).

(*  Pascal,  Phương án 2  *)

(***************************************

      To hop chap k cua n phan tu

              PHUONG AN 2

***************************************)

program ToHopKN;

uses crt;

const

  bl = #32; mn = 10;  fn = 'TOHOP.INP';  gn = 'TOHOP.OUT';

type

  mb1 = array[0..mn] of byte;

var

 x: mb1;

 n, k, v: byte;

 f,g: text;

 procedure Doc;

 begin

   assign(f,fn); reset(f); readln(f,n,k); close(f);

 end;

 function Next: Boolean;

   var i: byte;

 begin

   Next := false;

   if (v = 0) then exit;

   { Pha 2. Xep }

   x[v] := x[v] + 1;

   for i := v + 1 to k do x[i] := x[i-1] + 1;

   if (x[k] = n) then v := v - 1 else v := k;

   Next := true;

 end;

 procedure Run;

   var i: byte;

 begin

   Doc;

   assign(g,gn); rewrite(g);

   for i := 1 to k do x[i] := i;

   if (x[k] = n) then v := 0 else v := k;

   repeat

     for i := 1 to k do write(g,x[i],bl);

     writeln(g);

   until not Next;

   close(g);

 end;

 BEGIN

  Run;

 END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH