Liệt Kê Hoán Vị Tiếp Theo Theo Thứ Tự Từ Điển.

Liệt kê các hoán vị của tập phần tử. Cho . Hãy liệt kê các hoán vị từ n phần tử của X. Mỗi hoán vị từ phần tử của có thể biểu diễn bởi bộ có thứ tự n thành phần: thoả mãn ai ∈ X, I = 1, 2,.., n, ap≠ aq, p≠ q. từ n phần tử của X có thể xác định nhiều thứ tự khác nhau. Tuy nhiên, thứ tự dễ thấy nhất là thứ tự từ điển được định nghĩa như sau: Ta nói hoán vị đi trước hoán vị trong thứ tự từ điển và ký hiệu là , nếu tìm được chỉ số (1 ≤ k ≤ n) sao cho: đầu tiên thoả mãn . 

Tìm là số nhỏ nhất còn lớn hơn trong các số ở bên phải ; 

Đổi chỗ với  

Lật ngược đoạn từ đến . 

Chẳng hạn ta đang có hoán vị (3, 6, 2, 5, 4, 1), cần xây dựng hoán vị kế tiếp theo thứ tự từ điển.

1. Ta duyệt từ j = n-1 sang bên trái để tìm j đầu tiên thoả mãn aj < aj+1 ta nhận được j = 3 ( a3=2 <a4=5). 
2. Số nhỏ nhất còn lớn hơn a3 trong các số bên phải a3 là a5(a5=4). 
3. Đổi chỗ a3 cho a5 ta thu được (3, 6, 4, 5, 2, 1), 
4. Lật ngược đoạn từ a4 đến a6 ta nhận được (3,6,4,1,2,5). 

Chương trình cài đặt.
using namespace std; #define MAX 20 #define TRUE 1 #define FALSE 0 int X[MAX]; int n;//so phan tu cua mang int countHV;//biến đếm số hoán vị. int Stop;//biến dừng tìm kiếm hoán vị tiếp theo. void Init(void){ countHV = 0; cout<<"Nhap n="; //nhập các phần tử của mảng. for (int i = 1; i <= n; i++) X[i] = i; } void Result(void){ countHV++; cout<<"Hoan vi "<<countHV<<": "; for (int i = 1; i <= n; i++) cout<<X[i]; cout<<endl; } void Next_Permutaion(void){ int j, k, r, s, temp; j = n - 1; j--; if (j == 0) Stop = TRUE; else { k = n; //3. Đổi chỗ aj với ak temp = X[j]; X[j] = X[k]; X[k] = temp; r = j + 1; s = n; while (r < s){//4. Lật ngược đoạn từ aj+1 đến an. temp = X[r]; X[r] = X[s]; X[s] = temp; r++; s--; } } } void Permutation(void){ Stop = FALSE; while (!Stop){ Result(); Next_Permutaion(); } } void main(void){ Init(); Permutation(); getch(); } Output của chương trình với n = 4.

Nhap n = 4  Hoan vi 1: 1234  Hoan vi 2: 1243  Hoan vi 3: 1324  Hoan vi 4: 1342  Hoan vi 5: 1423  Hoan vi 6: 1432  Hoan vi 7: 2134  Hoan vi 8: 2143  Hoan vi 9: 2314  Hoan vi 10: 2341  Hoan vi 11: 2413  Hoan vi 12: 2431  Hoan vi 13: 3124  Hoan vi 14: 3142  Hoan vi 15: 3214  Hoan vi 16: 3241  Hoan vi 17: 3412  Hoan vi 18: 3421  Hoan vi 19: 4123  Hoan vi 20: 4132  Hoan vi 21: 4213  Hoan vi 22: 4231  Hoan vi 23: 4312  Hoan vi 24: 4321  

Liệt kê các hoán vị của tậpphần tử. Cho. Hãy liệt kê các hoán vị từ n phần tử của X.Mỗi hoán vị từphần tử củacó thể biểu diễn bởi bộ có thứ tự n thành phần:thoả mãn ai ∈ X, I = 1, 2,.., n, ap≠ aq, p≠ q.Trên tập cáctừ n phần tử của X có thể xác định nhiều thứ tự khác nhau. Tuy nhiên, thứ tự dễ thấy nhất là thứ tự từ điển được định nghĩa như sau: Ta nói hoán vịđi trước hoán vịtrong thứ tự từ điển và ký hiệu là, nếu tìm được chỉ s&# 7889;(1 ≤ k ≤ n) sao cho:Chẳng hạn X = { 1, 2, 3, 4}. Các hoán vị các phần tử của X được liệt kê theo thứ tự từ điển {1 2 3 4}, {1 2 4 3}, {1 3 2 4}, {1 4 2 3}, {1 4 3 2}, {2 1 3 4}, {2 1 4 3}, {2 3 1 4}, {2 3 4 1}....{4 3 2 1}.Như vậy, hoán vị đầu tiên trong thứ tự từ điển là (1, 2, …, n) và hoán vị cuối cùng là (n, n- 1,..., 1). Giả sử a = a1a2... an là một hoán vị chưa phải là cuối cùng. Khi đó ta có thể chứng minh được rằng, hoán vị kế tiếp trong thứ tự từ điển có thể xây dựng bằng cách thực hiện các qui tắc biến đổi sau &# 273;ối với hoán vị hiện tại:Chẳng hạn ta đang có hoán vị (3, 6, 2, 5, 4, 1), cần xây dựng hoán vị kế tiếp theo thứ tự từ điển.Chương trình cài đặt.Output của chương trình với n = 4.