[Thuật toán] Liệt kê hoán vị tiếp theo theo thứ tự từ điển.

Bài toán : Liệt kê các hoán vị của tập n phần tử. Cho X = { 1, 2,.., n }. Hãy liệt kê các hoán vị từ n phần tử của X.
Thuật toán: Mỗi hoán vị từ n phần tử của X có thể biểu diễn bởi bộ có thứ tự n thành phần: a = (a1, a2,.., an) thoả mãn ai ∈ X, I = 1, 2,.., n, ap≠ aq, p≠ q.
Trên tập các hoán vị 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ị a = a1a2... an đi trước hoán vị a’ = a1’a2’...an’ trong thứ tự từ điển và ký hiệu là a < a', nếu tìm được chỉ số k (1 ≤ k ≤ n) sao cho: a1 = a1', a2 = a2',....,ak < ak'.
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 đối với hoán vị hiện tại:

1. Tìm từ phải qua trái hoán vị có chỉ số j đầu tiên thoả mãn aj< aj+1. 
2. Tìm ak là số nhỏ nhất còn lớn hơn aj trong các số ở bên phải aj; 
3. Đổi chỗ aj với ak 
4. Lật ngược đoạn từ aj+1 đến an. 

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.

#include<conio.h>
#include<iostream>
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=";
 cin>>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;
 while (j > 0 && X[j] > X[j + 1])//1. tìm từ trái qua phải chỉ số j thỏa mãn aj< aj
  j--;
 if (j == 0)
  Stop = TRUE;
 else {
  k = n;
  while (X[j] > X[k]) k--;//2.Tìm ak là số nhỏ nhất còn lớn hơn aj trong các số ở bên phải aj; 
  //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

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.