Thuật toán sinh kế tiếp – 1. Liệt kê các hoán vị của n phần tử

 Thuật toán sinh kế tiếp 1

 Liệt kê các hoán vị của n phần tử

Bài toán: Cho tập hợp X = {1, 2, …, n} . Hãy liệt kê tất cả các hoán vị của X.

Ví dụ: {1, 2, 3, 4} khi đó các hoán vị của 4 phần tử được sắp xếp theo thứ tự từ điển như sau:

• Như vậy hoán vị đầu tiên là 1, 2, 3, …, n, hoán vị cuói cùng là n, n-1, …, 1

Thuật toán sẽ làm như sau:

Ví dụ :

1	2	3	4
1	2	4	3
1	3	2	4
1	3	4	2
1	4	2	3
1	4	3	2
2	1	3	4
2	1	4	3
2	3	1	4
2	3	4	1
2	4	1	3
2	4	3	1
3	1	2	4

• Nội dung thuật toán

1. Tìm từ phải qua trái vị trí có chỉ số j đầu tiên thỏa mãn a_j < a_j+1
2. Tìm a_k là số nhỏ nhất còn lớn hơn a_j trong các số bên phải a_j
3. Đổi chỗ a_j cho a_k
4. Lật ngược đoạn a_j+1, …, a_n.

Phân tích ví dụ :

• Phân tích hàng thứ nhất -> hàng thứ 2:

1. Vt đầu tiên thỏa mãn số sau lớn hơn số trước là ở vt thứ 3 a₃=3_.
2. Ở vị trí a₄ = 4 là giá trị nhỏ nhất mà vẫn lớn hơn a₃ = 3.
3. Thưc hiện đổi chỗ a₃ cho a₄. Ta được dãy 1  2  4  3
4. Vì nó đã ở vị trí cuối cùng nên không cần lật ngược.

• Phân tích ở hàng thứ 2 -> hàng thứ 3:

1. Vt đầu tiên thỏa mãn số sau lớn hơn số trước là ở vt thứ 2 a₂=2
2. Ở vị trí a₄ = 3 là giá trị nhỏ nhất bên phải a₂ và lớn hơn a₂
3. Đổi chỗ a₂  cho a₄ ta được 1  3   4   2
4. Lật ngược từ a_j+1 tức vị trí thứ 3 thì ta được dãy 1 3  2  4 như trong dãy 3.

• Ta có thể thấy rằng điều kiện sô nhỏ nhất nằm bên phải a­_j chỉ cần tìm từ bên phải sang trái số nào lớn hơn a_{j ­}được tìm thấy đầu tiền thì đó chính là giá trị cần tìm, tính chất của dãy đã giúp ta bỏ được công đoạn này.

Cài đặt code : Souce code