Link Sub: http://www.spoj.com/PTIT/problems/BCPERMU/
Người Gửi: Dương Lee
- Problem:
Liệt kê hoán vị của n phần tử của một tập gồm các số từ 1->n.Input
Dòng duy nhất chứa số n (1<=n<=8)
Output
Các hoán vị sắp xếp theo thứ tự từ điển tăng dần.
Example:
Các hoán vị sắp xếp theo thứ tự từ điển tăng dần.
Input
3
Output:
123
132
213
231
312
321
- Solution:
Code C: - Sinh hoán vị thông thường:
+ Khởi tạo cấu hình ban đầu: 1 2 3 ... n
+ Tìm vt mà tại đó dãy mất tính tăng (vt: n-1 -> 0): Nếu không tìm thấy thì dãy đã đạt cấu hình cuối (Kết thúc).
+ Tìm phần tử [i] đầu tiên > phần tư [vt] và đổi chỗ chúng (i: n-1 -> 0).
+ Sau khi đổi chỗ thì cập nhập lại tất cả các phần tử sau vt tăng dần (i: vt+1 -> n-1).