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 Tran 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
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

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

 
Status trên Facebook lập kỷ lục khó tin

Status trên Facebook lập kỷ lục khó tin

Số ký tự cho phép trong một lần cập nhật trạng thái đã tăng lên ngưỡng 63.206 rồi nhé!

Hướng dẫn thêm 1 pseudo field trong Drupal 7

Hướng dẫn thêm 1 pseudo field trong Drupal 7

Sometimes you need to display a field that have no input, like a static text or image on each node, or a Facebook like button, or whatever that does not have an input, but you still want to display it as a field, for that you have the hook hook_field_extra_fields.

Nhân viên cũ của Palm nói xấu WebOS

Nhân viên cũ của Palm nói xấu WebOS

Giám đốc phụ trách phát triển phần mềm của Palm - Paul Mercer, cùng một số nhân viên khẳng định WebOS đã đi sai hướng,

BLOG POSTS

 

Wordpress Freelancer

 

Wordpress Freelancer