tailieunhanh - CTDL 2005 chuong 17

| Chương 17 - Ung dụng sinh các hoán vị Chương 17 - ỨNG DUNG SINH CẤC HOÁN VỊ Ung dụng này minh họa sự sử dụng cả hai loại danh sách danh sách tong quát va DSLK trong mang liên tục. Ung dụng nay se sinh ra n each hoan vị cua n đối tượng một cach hiêu qua nhất. Chung ta goi cac hoan vị cua n đối tượng khac nhau la tất ca cac phượng an thiết lạp chung theo moi thứ tự co thê9 co. Chung ta co thê chon bất ky đoi tượng nao trong n đoi tượng đat tai vị trí đầu tiên sau đo co thê chon bất ky trong n-1 đoi tượng con lai đạt tai vị trí thứ hai va cứ thế tiếp tuc. Cac chon lựa nay đọc lạp nhau nên tong so cach chon lựa la n x n-1 x n-2 x . x 2 x 1 n Hình Sinh cac hoan vị cho 1 2 3 4 . Y tưởng Chung ta xac định cac hoan vị qua cac nut trên cay. Đau tiên chỉ co 1 ợ goc cay. Chung ta co hai hoan vị cua 1 2 bang cach ghi 2 bên trai sau đo bên phai cua 1. Tượng tự sau hoan vị cua 1 2 3 co được từ 2 1 va 1 2 bang cach thêm 3 vao ca ba vị trí co thê trai giưa phai . Như vậy cac hoan vị cua 1 2 . k co được như sau Đối vơi mỗi hoán vị cụá 1 2 . k-1 chung tá đưá các phán tư váo một list. Sáụ đó chen k váo mội vị trí cỗ thể trong list đó để cỗ được k hoán vị khác nháụ cụá 1 2 . k . Giai thuat nay minh hoa viêc sử dung đê quy đê hoan thanh cac cong viêc đa tam hoan. Chung ta sê viết mot ham đau tiên la thêm 1 vao mot danh sach rong Giao trình Cấu trúc dữ liệu và Giải thuật 395 Chương 17 - Ung dụng sinh các hoán vị sau đó gọi đệ quy để thêm lần lượt các so khác từ 2 đến n vào danh sách. Lan gọi đệ quy đàu tiên sê thêm 2 vào danh sách chỉ chưa có 1 già sử thêm 2 bên trài cua 1 và trì hoàn càc khà nàng thêm khàc như là thêm 2 bên phai cua 1 đê9 gọi đê quy tiếp. Cuối cung làn goi đê quy thứ n sê thêm n vào danh sàch. Bàng càch này bàt đàu từ một cấu truc cày chung tà phàt triê9n một giai thuàt trong đo cày này trô thành mot cày đê quy. . Tinh chế Chung ta sê phàt 11 giai thuàt trên cu thê hợn. Hàm thêm càc 1 đến n đê sinh n hoàn vị sê được goi như sau permute 1 n .