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

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

Bạn thấy bài viết này như thế nào?: 
Average: 10 (8 votes)
Ảnh của Tommy Tran

Tommy owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
15 Framework HTML5/CSS3 Tốt cho Nhà Thiết Kế

15 Framework HTML5/CSS3 Tốt cho Nhà Thiết Kế

Framework giúp cho nhà thiết kế có thể tiết kiệm được rất nhiều thời gian. Bài viết dưới đây tập hợp những framework hỗ trợ HTML5 và CSS3 tốt nhất

 

10 công cụ Joomla miễn phí tốt nhất

10 công cụ Joomla miễn phí tốt nhất

Joomla là một trong những CMS phổ biến nhất thế giới, được sử dụng trên hơn 30 triệu site với hơn 200.000 user cộng đồng và có vô số công cụ.

 Webmaster và Kiến thức quảng bá Web, Tối ưu Website cho Google

Webmaster và Kiến thức quảng bá Web, Tối ưu Website cho Google

Phân tích các câu hỏi thường gặp của Webmaster và đưa ra các giải pháp tối ưu cho công cụ tìm kiếm Google.

Tomdesgin.vn

 

Drupal Services