Giải thuật liệt kê hoán vị - 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