Tham khảo tài liệu 'cấu trúc dữ liệu 2005 p17', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chương 17 - Ung dung 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 sẽ sinh ra n cach 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 thêo moi thứ tự co thê9 co. Chung ta co thế chon bất ky đoi tượng nao trong n đoi tượng đặt tai vị trí đầu tiên sau đo co thế chon bất ky trong n-1 đoi tượng con lại đạt tại 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 các hoán vị cho 1 2 3 4 . Y tưởng Chung tá xác định các hoán vị quá các nut trên cáy. Đáu tiên chỉ co 1 ỗ gốc cáy. Chung tá co hái hoán vị cuá 1 2 báng cách ghi 2 bên trái sáu đo bên phái cuá 1. Tưỗng tự sáu hoán vị cuá 1 2 3 co đưỗc từ 2 1 vá 1 2 báng cách thêm 3 váo cá bá vị trí co thê trái giưá phái . Như váy các hoán vị cuá 1 2 . k co đưỗc như sáu Đối vơi moi hoán vị củá 1 2 . k-1 chung tá đưá các phán tư váo một list. Sáu đó chen k váo moi vị trí co thể trong list đó để co đượ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 hoãn. Chung ta sê viết mọt ham đầu tiên la thêm 1 vao mọt 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 đo goi đe quy đe9 them lan lượt cac so khac từ 2 đến n vao danh sach. Lan goi đe quy đau tien se them 2 vao danh sach chỉ chöa co 1 gia sử them 2 ben trai cua 1 va trì hoan cac kha nang them khac như la them 2 ben phai cua 1 đe9 goi đe quy tiếp. Cuối cung lan goi đe quy thứ n se them n vao danh sach. Bang cach nay bat đau từ mọt cấu truc cay chung ta phat triê9n mọt giai thuật trong đo cay nay trô thanh một cay đe quy. . Tinh chế Chung ta sẽ phát triển giải thuật trên cụ thể hơn. Hàm thêm các sO từ 1 đến n để sinh n hoàn vị sê đừơc gọi nhừ sau permute 1 n Gia .
