Tin học Tây Sơn


Join the forum, it's quick and easy

Tin học Tây Sơn
Tin học Tây Sơn
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Thuật toán sinh hoán vị

Go down

Thuật toán sinh hoán vị Empty Thuật toán sinh hoán vị

Bài gửi by Admin Mon Jan 18, 2021 10:33 am

Ta sẽ lập chương trình liệt kê các hoán vị của n phần tử {1, 2, …, n} theo thứ tự từ điển.
Ví dụ với n = 3, ta phải liệt kê đủ 6 hoán vị:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Như vậy hoán vị đầu tiên sẽ là 〈1, 2, …, n〉. Hoán vị cuối cùng là 〈n, n-1, …, 1〉.
Hoán vị sẽ sinh ra phải lớn hơn hoán vị hiện tại, hơn thế nữa phải là hoán vị vừa đủ lớn hơn hoán vị hiện tại theo nghĩa không thể có một hoán vị nào khác chen giữa chúng khi sắp thứ tự. Giả sử hoán vị hiện tại là a = 〈3, 2, 6, 5, 4, 1〉, xét 4 phần tử cuối cùng, ta thấy chúng được xếp giảm dần, điều đó có nghĩa là cho dù ta có hoán vị 4 phần tử này thế nào, ta cũng được một hoán vị bé hơn hoán vị hiện tại. Như vậy ta phải xét đến a[2] = 2, thay nó bằng một giá trị khác. Ta sẽ thay bằng giá trị nào?, không thể là 1 bởi nếu vậy sẽ được hoán vị nhỏ hơn, không thể là 3 vì đã có a[1] = 3 rồi (phần tử sau không được chọn vào những giá trị mà phần tử trước đã chọn). Còn lại các giá trị 4, 5, 6. Vì cần một hoán vị vừa đủ lớn hơn hiện tại nên ta chọn a[2] = 4. Còn các giá trị (a[3], a[4], a[5], a[6]) sẽ lấy trong tập {2, 6, 5, 1}. Cũng vì tính vừa đủ lớn nên ta sẽ tìm biểu diễn nhỏ nhất của 4 số này gán cho a[3], a[4], a[5], a[6] tức là 〈1, 2, 5, 6〉. Vậy hoán vị mới sẽ là 〈3, 4, 1, 2, 5, 6〉.
Ta có nhận xét gì qua ví dụ này: Đoạn cuối của hoán vị hiện tại được xếp giảm dần, số a[5] = 4 là số nhỏ nhất trong đoạn cuối giảm dần thoả mãn điều kiện lớn hơn a[2] = 2. Nếu đổi chỗ a[5] cho a[2] thì ta sẽ được a[2] = 4 và đoạn cuối vẫn được sắp xếp giảm dần. Khi đó muốn biểu diễn nhỏ nhất cho các giá trị trong đoạn cuối thì ta chỉ cần đảo ngược đoạn cuối. Trong trường hợp hoán vị hiện tại là 〈2, 1, 3, 4〉 thì hoán vị kế tiếp sẽ là 〈2, 1, 4, 3〉. Ta cũng có thể coi hoán vị 〈2, 1, 3, 4〉 có đoạn cuối giảm dần, đoạn cuối này chỉ gồm 1 phần tử (4) Vậy kỹ thuật sinh hoán vị kế tiếp từ hoán vị hiện tại có thể xây dựng như sau:


Bước 1: Xác định đoạn cuối giảm dần dài nhất, tìm chỉ số i của phần tử a[i] bắt đầu đoạn cuối đó. Điều này đồng nghĩa với việc tìm từ vị trí cuối dãy lên đến phần tử thứ 2 (vì nếu tìm được ở phần tử đầu tiên tức đó là hoán vị cuối cùng rồi nên không cần), gặp chỉ số i đầu tiên thỏa mãn a[i-1] < a[i].
Bước 2: Nếu tìm thấy chỉ số i như trên
– Trong đoạn cuối giảm dần, tìm phần tử a[k] nhỏ nhất thoả mãn điều kiện a[k] > a[i-1]. Do đoạn cuối giảm dần, điều này thực hiện bằng cách tìm từ cuối dãy lên đầu gặp chỉ số k đầu tiên thoả mãn a[k] > a[i-1] (có thể dùng tìm kiếm nhị phân).
– Đảo giá trị a[k] và a[i-1]
– Lật ngược thứ tự đoạn cuối giảm dần (từ a[i] đến a[k]) trở thành tăng dần.
Bước 3: Nếu không tìm thấy tức là toàn dãy đã sắp giảm dần, đây là cấu hình cuối cùng.


Bài tâp: Hãy viết thủ tục sinh ra các hoán vị của dãy n số. n được nhập từ bàn phím.



Code:
Program Hoan_vi;
Uses crt;
Type Mang=array[1..100] of integer;
Var n:integer;
    a:Mang;
//-------------------
Procedure Nhap;
Var i:integer;
Begin
Write('N=');readln(n);
For i:=1 to n do
        a[i]:=i;
For i:=1 to n do
        write(a[i]);
Writeln;
End;
//-------------------
Procedure Doi(Var x,y:integer);
Var Tam:integer;
Begin
Tam:=x;
x:=y;
y:=Tam;
End;
//-------------------
Procedure  S_hv(Var a:mang);
Var i,j,k,v,t:integer;
Begin
For i:=n downto 2 do
        If a[i]>a[i-1] then
                begin
                t:=i;
                break;
                end;
For k:=n downto t do
        If a[k]>a[t-1] then
                begin
                v:=k;
                break;
                end;
Doi(a[t-1],a[v]);
        For k:=t to n-1 do
                For j:=k+1 to n do
                        If a[j]<a[k] then Doi(a[j],a[k]);
End;
//-------------------
Function Giam(a:Mang):boolean;
Var i,j:integer;
Begin
Giam:=false;
For i:=1 to n do
        For j:=i+1 to n do
                If a[j]>a[i] then exit;
Giam:=true;
End;
//-------------------
Procedure in_hv;
Var i:integer;
Begin
While not Giam(a) do
        begin
        S_hv(a);
        For i:=1 to n do
                Write(a[i]);
        Writeln;
        end;
End;
//-------------------
BEGIN
CLRSCR;
Nhap;
in_hv;
READLN;
END.
Admin
Admin
Admin
Admin

Posts : 954
Points : -8013
Reputation : -10042
Join date : 16/11/2015
Age : 31

https://tinhocts.forumvi.com

Về Đầu Trang Go down

Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết