Liệt kê hoán vị (PP Sinh)

Link bài: http://www.spoj.com/PTIT/problems/BCPERMU/

9807. Liệt kê hoán vị (Cơ bản)

Mã bài: BCPERMU

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

Input:
3

Output:
123
132
213
231
312
321

 

HD:

-Xây dựng một thứ tự các hoán vị cần liệt kê 

Một hoán vị có thể biể diễn bởi một bộ có thứ tự a=(a1,a2,…,an) : athuộc {1,2,…,n} và ai ≠ aj, với mọi i  ≠  j.

Gọi a,b là hai tập con n phần tử. Ta xây dựng một thứ tự như sau:

a<b <=> tồn tại a1=b1,…,ak-1=bk-1,ak<bk. Ví dụ: n=4, (2,1,4,3) < (2,3,1,4)

Suy ra hoán vị đầu tiên là (1,2,…,n) và hoán vị cuối cùng là (n,n-1,…,1)

-Xây dựng thuật toán sinh hoán vị kế tiếp

Gọi a=(a1,a2,…,an) là hoán vị hiện tại

Nếu a=(n,n-1,…,1) thì đây là hoán vị cuối cùng, gán stop=1;

Ngược lại:

  • Tìm ai đầu tiên từ phải qua trái sao cho a< ai+1
  • Tìm ak là số nhỏ nhất trong các số bên phải ai mà ak > ai
  • Hoán vị ai và ak.
  • Đảo ngược dãy con từ ai+1 tới an

Code tham khảo: 

 

Share
Share