//
you're reading...
00 - Chủ đề chung, Bài tập huấn luyện

Tệp các hoán vị


Đề bài


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.

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:

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.
// C#
using System;
using System.Collections.Generic;
using System.Text;

Sáng tạo trong Thuật toán và Lập trình Tập I 46
using System.IO;
namespace SangTao1
{
class GenAllPer
{
static void Main(string[] args)
{
string fn = “HoanVi.txt”;
int d = Gen(fn,5);
Test(fn,d); // Xem kết quả
Console.WriteLine(“\n Fini “);
Console.ReadLine();
}
// Sinh các hoán vị, ghi file fn
static public int Gen(string fn, int n)
{
if (n < 1 | n > 9) return 0;
int d = 0; // dem so hoan vi d = n!
StreamWriter f = File.CreateText(fn);
int[] a = new int[n + 1];
for (int i=0; i <= n; ++i) a[i]=i;
do { // Ghi file
for (int i=1; i <= n; ++i)
f.Write(a[i] + ” “);
f.WriteLine(); ++d;
} while (Next(a));
f.Close();
return d;
}
static bool Next(int[] a)//Hoán vị tiếp
{
int i, j, t, n = a.Length-1;
for (i=n-1; a[i] > a[i+1];–i) ;
if (i == 0) return false;
for (j = n; a[j] < a[i]; –j) ;
t = a[i]; a[i] = a[j]; a[j] = t;
for (++i, j = n; i < j; ++i, –j)
{ t = a[i]; a[i] = a[j]; a[j] = t; }
return true;
}
static public void Test(string fn, int d)
{
Console.WriteLine(“\n Tong cong ”
+ d + ” so”);
Console.WriteLine(File.ReadAllText(fn));
}
} // GenAllPer
} // SangTao1

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: