Các hoán vị

Liệt kê tăng dần theo thứ tự từ điển các hoán vị của các số 1..N.

Dữ liệu vào: tệp văn bản HV.INP chứa duy nhất  số  N, 1 £ N £ 9. Dữ liệu ra: tệp văn bản HV.OUT Mỗi dòng một hoán vị.	HV.INP	HV.OUT
	3	1 2 3  1 3 2  2 1 3  2 3 1  3 1 2  3 2 1

Thuật toán

Sử dụng hàm Next trong bài trước. Khởi trị cho x là hoán vị đơn vị x = (1,2,…,N).

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

Trong các chương trình dưới đây ta xây dựng các hàm Next không có tham biến nhằm mục đích đẩy nhanh quá trình tính toán. Như vậy, dữ liệu được cho dưới dạng các biến tổng thể, bao gồm n  -  chiều dài của các hoán vị, x[0..n-1] - mảng chứa hoán vị.

(*  Pascal  *)

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

    Liet ke cac hoan vi cua 1..N

    theo thu tu tang dan

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

program CacHoanVi;

uses crt;

const

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

type

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

var

 x: mb1; { chua hoan vi }

 n: byte; { Len(x) }

 f,g: text; { input, output files }

 procedure Doc;

 begin

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

 end;

 function Next: Boolean;

   var i,j,t : byte;

 begin

   Next := false;

   { Tim diem gay }

   i := n - 1;

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

   { x[i] < x[i+1] }

   if (i = 0) then exit;

   j := n;

   while (x[j] <= x[i]) do j := j - 1;

   t := x[i]; x[i] := x[j]; x[j] := t;

   i := i + 1; j := n;

   while (i < j) do

     begin

       t := x[i]; x[i] := x[j]; x[j] := t;

       i := i + 1; j := j - 1;

     end;

   Next := true;

 end;

 procedure Run;

   var i: byte;

 begin

   Doc; x[0] := 0; // Dat linh canh

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

   for i := 1 to n do x[i] := i;// Hoan vi don vi

   repeat

     for i := 1 to n 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