Tệp các hoán vị

Tệp các hoán vị

               Với mỗi số n cho trước trong khoảng 1..9, ghi vào một tệp văn bản có tên cho trước toàn bộ các hoán vị của 1..n. Hoán vị được sắp xếp tăng theo thứ tự từ điển, thí dụ 21345 < 21354.

Thuật toán

1. Khởi tạo và ghi hoán vị nhỏ nhất là hoán vị đơn vị s [1..n] = (1,2,...,n).

2. Giả sử ta đã ghi được hoán vị s[1.n] vào tệp. Hoán vị tiếp theo được tạo từ s thông qua hàm Next như sau:

2.1 Tìm điểm gãy: Tìm ngược từ s[n] trở về trước đến vị trí i đầu tiên thoả điều kiện s[i] < s[i + 1].

-          Nếu không tìm được i tức là s là hoán vị lớn nhất, s[1..n] = (n,n-1,..,1). Đặt trị false cho hàm Next và dừng thuật toán. Next = false có nghĩa là không tồn tại hoán vị sát sau hoán vị s hay s là hoán vị lớn nhất. 

-          Nếu tìm được: thực hiện bước 2.2.

2.2 Tìm điểm vượt: Tìm ngược từ s[n] trở về trước đến vị trí j đầu tiên thoả điều kiện s[j] > s[i].

2.3. Đổi chỗ  s[i] với s[j].

2.4. Lật:  Đảo lại trật tự của dãy s[i + 1..n] ta sẽ thu được hoán vị đứng sát sau hoán vị s.

3. Đặt trị true cho hàm Next. Next = true có nghĩa là tìm được hoán vị sát sau hoán vị s. 

Gia sư tin học xin Chú ý

Khi khởi trị hoán vị đơn vị ta sử dụng phần tử s[0] = 0 làm lính canh. Nhờ vậy, khi duyệt ngược để tìm điểm gãy ta không phải kiểm tra giới hạn mảng. Thay vì viết

i := n-1;

while (i > 0) and (s[i] > s[i+1]) do i:= i-1;

ta chỉ cần viết

i := n-1;

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

Hàm Next được mô tả như sau:

function  Next(n: integer): Boolean;

var   i, j, t: integer;

begin

Next := false; i := n-1;

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

if i = 0 then exit;

{ s[i] < s[i+1], i là điểm gãy }

j := n; { Tìm điểm vượt a[j] > a[i] }

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

{ Đổi chỗ s[i] , s[j] }

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

{ Lật s[i+1..n] } i:= i+1; j:= n;

while i < j do

begin

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

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

end;

Next:= true;

end;

Thí dụ, với n = 8, giả sử ta đã ghi được hoán vị s = 74286531, khi đó hoán vị sát sau s sẽ được xây dựng như sau:

	j	k	w	m	n	o	{	q
S	7	4	2	8	6	5	3	1
Tìm điểm gãy: i = 3, vì s[3] < s[4]	7	4	2	8	6	5	3	1
Tìm điểm vượt:  j = 7, vì s[7] > s[3]	7	4	2	8	6	5	3	1
Đổi chỗ điểm gãy và điểm vượt: s[3] « s[7]	7	4	3	8	6	5	2	1
Lật đoạn s[4..8]	7	4	3	1	2	5	6	8
Quy trình hoạt động của hàm Next 74286531 Þ 74312568

(*  Pascal  *)

program GenAllPer;

{$B-}

uses crt;

const MN = 9; {max n} BL = #32; {dau cach}

var   s: array[0..MN] of integer;

function  Next(n: integer): Boolean; tự viết

procedure Gen(n: integer);

const

      fn = 'HoanVi.dat'; {ten tep ket qua}

var

      d: longint; {dem so luong hoan vi}

      i: integer;

      f: text; {tep ket qua}

begin

if (n < 1) or (n > MN) then exit;

assign(f,fn); rewrite(f);

d := 0; {dem so hoan vi}

       {Sinh hoán vị đơn vị. Đặt lính canh s[0] = 0}

for i := 0 to n do s[i]:= i;

repeat

d := d+1; {Ghi hoan vi thu d, s vao tep}

   for i:= 1 to n do write(f, s[i], BL);

   writeln(f);

until not (next(n));

writeln(f,' Tong cong ',d, ' hoan vi');

close(f);

end;

BEGIN

Gen(5); write('fini'); readln;

END.