Dãy các hoán vị

Dãy các hoán vị của N chữ cái HOA đầu tiên trong bảng chữ tiếng Anh được sắp theo trật tự từ điển tăng dần và viết liền nhau thành một dãy kí tự duy nhất. Hãy cho biết kí tự thứ M trong dãy tính từ 1 trở đi, 2 £ N £ 10, 1 £ M £ N.N!. Thí dụ, với N=3, ta có dãy 6 hoán vị xếp theo trật tự từ điển là ABC, ACB, BAC, BCA, CAB, CBA. Sau khi ghép chúng ta thu được dãy duy nhất gồm 18 kí tự ABCACBBACBCACABCBA. Kí tự thứ M = 15 trong dãy là: B.

 Thuật toán

Nếu ta viết mỗi hoán vị trên 1 dòng thì kí tự thứ M sẽ nằm trên dòng d = (M-1) div N (tính từ dòng 0) và sẽ chiếm vị trí v = ((M-1) mod N)+1 (tính từ 1) trên dòng d đó. Như vậy ta cần  xác định hoán vị trên dòng d rồi lấy kí tự nằm ở vị trí v làm kết quả.

Để xác định hoán vị (c₁,c₂,...,c_N) tại dòng d ta lần lượt tính các kí tự c_i, i = 1..N. Ta phân hoạch các hoán vị theo nhóm. Nếu bỏ kí tự đầu tiên thì ta còn lại (N-1)! hoán vị, khi đó hoán vị tại dòng d sẽ rơi vào nhóm d div (N-1)! và sẽ chiếm dòng d mod (N-1)! trong nhóm đó. Tương tự, ta tính cho các kí tự thứ 2, 3, ..., N-1. Kí tự còn lại sẽ chiếm vị trí thứ N. Nếu biết nhóm d của kí tự thứ i trong hoán vị thì ta tính được chính kí tự đó như sau.

   d = 1 ứng với kí tự thứ nhất trong số các kí tự chưa dùng,

   d = 2 ứng với kí tự thứ hai trong số các kí tự chưa dùng,

   ...

Tổng quát, d ứng với kí tự thứ d trong số các kí tự chưa dùng.

Mỗi lần xác định được kí tự nào thì ta đánh dấu kí tự đó bằng thủ tục Mark.

Để tránh việc tính n! ta viết thủ tục ThuongDu(z, n, q, r) cho ra thương q và dư r của phép chia số tự nhiên z cho n!, cụ thể là q = z div n! và r = z mod n!.  Thủ tục này khá đơn giản. Ta có

q₁ = z div n; r₁ = z mod n Þ z = q₁.n + r₁;

q₂ = q₁ div (n-1); r₂ = q₁ mod (n-1) Þ q₁ = q₂.(n-1) + r₂;

…

q_n-1 = q_n-2 div 2; r_n-1 = q_n-2 mod 2 Þ q_n-2 = q_n-1.2 + r_n-1.

q_n = q_n-1 div 1 = q_n-1; r_n = q_n-1 mod 1 = 0.

Thay lần lượt các đại lượng của dòng dưới vào dòng trên ta thu được q = q_n-1 và r = r₁ + n.r₂ + (n-1).r₃ +…+ 3.r_n-1 + 2.r_n. Nhận xét này cho phép ta xây dựng thủ tục theo kỹ thuật chia liên tiếp như sau.

 procedure ThuongDu(z,n: longint;var q,r: longint);

    var c: longint;

   begin

     r := 0; q := z; c := 1;

     while n > 1 do

       begin

         r := r + (q mod n)*c;

         q := q div n;

         c := n; n := n - 1;

       end;

   end;

Thủ tục Test trong chương trình dưới đây tính mọi xuất hiện của các kí tự (M = 1..24*4) trong  dãy các hoán vị với N = 4.

Chương trình Pascal

(* Pascal *)

   uses crt;

   const MN = 20; bl = #32;

   var   b: array[0..MN] of byte;

   { d = z div n! r = z mod n! }

   procedure ThuongDu(z,n: longint;var q,r: longint);

    Tự viết

   { Danh dau ki tu v thu k

      trong so cac ki tu chua dung }

   procedure Mark(N,k,v: integer);

    var i,d: integer;

    begin

      d := 0;

      for i := 1 to N do

        if b[i] = 0 then

         begin

           d := d+1;

           if d = k then

            begin

              b[i] := v;

              exit;

            end;

         end;

    end;

   { Xac dinh ki tu thu M trong day cac hoan vi }

   function Value(N: integer;M: longint): char;

    var i,j,v: integer;

        th,du,d: longint;

   begin

      fillchar(b,sizeof(b),0);

      d := (M-1) div N; { Dong chua ki tu M }

      v := (M-1) mod N + 1; { vi tri cua M tren dong d }

      { xac dinh hoan vi tai dong d }

      j := N-1;

      for i := 1 to N-1 do

       begin

         ThuongDu(d,j,th,du);

         Mark(N, th+1,i);

         j := j-1;

         d := du;

       end;

      Mark(N,1,N);

      for i:=1 to N do

        if b[i] = v then

        begin

          Value := chr(ord('A') + i-1);

          exit;

        end;

   end;

   procedure Test;

     var N: integer;

         M: longint;

   begin

     N := 4; writeln;

     for M := 1 to 24*N do

       begin

        write(Value(N,M));

        if M mod N = 0 then

         begin

           if readkey = #27 then halt else writeln;

         end;

       end;

   end;

   BEGIN

     Test;

   END.

N	N!	N	N!
1 2 3 4 5 6 7 8 9 10	1 2 6 24 120 720 5040 40320 362880 3628800	11 12 13 14 15 16 17 18 19 20	39916800 479001600 6227020800 87178291200 1307674368000 20922789888000 355687428096000 6402373705728000 121645100408832000 2432902008176640000
Giai thừa của 20 số nguyên dương đầu tiên

Với C# bạn có thể dùng kiểu int64 hoặc long với 64 bit (8 byte) biểu diễn số nguyên trong khoảng
[-9.223.372.036.854.775.808, 9.223.372.036.854.775.807].

Độ phức tạp

Thuật toán chỉ đòi hỏi N = 20 phép chia các số nguyên có tối đa 20 chữ số và gọi thủ tục Mark N lần, mỗi lần gọi phải thực hiện phép duyệt trên dãy N phần tử. Tổng cộng là N² phép toán, tức là cỡ 400 phép toán thay vì 2432902008176640000 phép toán nếu ta sinh lần lượt N! hoán vị bằng phương pháp vét cạn với N = 20.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH