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?: 
No votes yet
Ả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: asaleotestf@gmail.com
  • 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

 
Người dùng Việt đang biến hashtag thành trò spam nhảm

Người dùng Việt đang biến hashtag thành trò spam nhảm

Hashtag đang là một chủ đề hot trên mọi ngóc ngách của Facebook trong hai ngày qua. Tuy nhiên tính nay này đang bị “lạm dụng” một cách vô tội vạ, khiến Facebook trở nên xấu xí, và đi chệch những định hướng dành cho tính năng này.

Video: Installing Drush on Mac OS X

Video cài đặt Drush trên Mac OS X

Last weekend we made a video that shows, hopefully, how easy it is to install Drush, the fabulously powerful command line tool that can drastically speed up developing, installing and maintaining Drupal sites. If you're worried about command line, don't fret. You can type, right? Then you can do command line!

State of Drupal presentation (June 2014)

Dries Buytaert phát biểu về State của Drupal presentation tại DrupalCon Austin

I gave my traditional State of Drupal presentation this week at DrupalCon Austin.