[Bài toán] Liệt kê các hoán vị của tập n phần tử bằng thuật toán Back Track

     Biểu diễn hoán vị dưới dạng p1, p2,.., pn, trong đó pi nhận giá trị từ 1 đến n và pi≠pj với i≠j. Các giá trị từ 1 đến n lần lượt được đề cử cho pi, trong đó giá trị j được chấp nhận nếu nó chưa được dùng. Vì vậy, cần phải ghi nhớ với mỗi giá trị j xem nó đã được dùng hay chưa. Điều này được thực hiện nhờ một dãy các biến logic bj, trong đó bj= true nếu j chưa được dùng. Các biến này phải được khởi đầu giá trị true trong thủ tục Init. Sau khi gán j cho pi, cần ghi nhận false cho bj và phải gán true khi thực hiện xong Result hay Try(i+1). Hình sau mô tả cây tìm kiếm lời giải bài toán liệt kê hoán vị của 1, 2,.., n với n = 3.

Chương trình cài đặt.

#include  <stdio.h> 
#include  <conio.h> 
#include  <stdlib.h> 
#define MAX 100 
#define TRUE 1 
#define FALSE 0 
int P[MAX], B[MAX], n, count = 0;
void Init(void){
 int i;
 printf("\n Nhap n="); scanf("%d", &n);
 for (i = 1; i <= n; i++)
  B[i] = TRUE;
}
void Result(void){
 int i; count++;
 printf("\n Hoan vi thu %d:", count);
 for (i = 1; i <= n; i++)
  printf("%3d", P[i]);
 getch();
}
void Try(int i){
 int j;
 for (j = 1; j <= n; j++){
  if (B[j]) {
   P[i] = j;
   B[j] = FALSE;
   if (i == n) Result();
   else Try(i + 1);
   B[j] = TRUE;
  }
 }
}
void main(void){
 Init();
 Try(1);
}

[Bài toán] Liệt kê tất cả các hoán vị của n phần tử.

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.
Chương trình cài đặt bằng đệ quy quay lui.

//chương trình sẽ liệt kê tất cả các hoán vị của tập X={1,2,3,4} bằng phương pháp đệ quy quay lui.
//Kết quả của chương trình sẽ được ghi ra file HOANVI.OUT
#include<iostream>
using namespace std;
#define n 4 //Định nghĩa tập X gồm 4 phần tử X = {1,2,3,4}
int arr[n+1][2];//giá trị của arr[k][0] là mảng chứa các phần tử của mảng X  (1 <= k <= n+1)
    //giá trị của arr[k][1] là biến đánh dấu phần tử đó đã xuất hiện trong hoán vị hay chưa (1 <= k <= n+1)
int permute[n+1];// mảng 1 chiều ghi kết quả của các lần hoán vị.
void toPermute(int index){
 if(index > n){// nếu chỉ số trong bước lặp đệ quy lớn hơn n -> in ra kết quả hoán vị.
  for(int i=1;i<=n;i++){
   cout<<permute[i];
   if(i<n)cout<<",";
  }
  cout<<endl;
  return;
 }
 //Đệ quy để sinh ra hoán vị tiếp theo.
 for(int i=1;i<=n;i++){
  if(arr[i][1] == false){// kiểm tra phần tử i của tập X chưa xuất hiện trong hoán vị 
   permute[index] = arr[i][0];
   arr[i][1] = true;
   toPermute(index+1);
   arr[i][1] = false;
  }
 }
}
int main(){
 freopen("HOANVI.OUT","w",stdout);
 for(int i=1;i<=n;i++){
  arr[i][0] = i;
  arr[i][1] = false;
 }
 toPermute(1);
 return 0;
}

Output của chương trình

1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,2,3
1,4,3,2
2,1,3,4
2,1,4,3
2,3,1,4
2,3,4,1
2,4,1,3
2,4,3,1
3,1,2,4
3,1,4,2
3,2,1,4
3,2,4,1
3,4,1,2
3,4,2,1
4,1,2,3
4,1,3,2
4,2,1,3
4,2,3,1
4,3,1,2
4,3,2,1

[Bài toán] Liệt kê các hoán vị của một tập có lặp theo thứ tự từ điển

Để xem giải thuật liệt kê hoán vị bạn có thể xem tại đây.

Bài toán: Cho tập X gồm n chữ cái. X = {a,b,c,…} trong đó các chữ cái có thể lặp lại.

Hãy liệt kê các hoán vị của tập X trên theo thứ tự từ điển.

[Input]

Có thể có nhiều hơn một test case trong file dữ liệu đầu vào PERMUTATION.INP. Dòng đầu tiên ghi số test case T.

Theo sau là danh sách test case.

Các dòng tiếp theo là string đầu vào.

[OutPut]

Ghi ra file PERMUTATION.OUT liệt kê tất cả các hoán vị theo thứ tự từ điển.

[I/O Example]

Input
2
bbjd
abcd

Output 
bbdj ← in the order of b, b, d, and j
bbjd
bdbj
bdjb
bjbd
bjdb ← in the order of b, j, d, and b
dbbj
dbjb
djbb
jbbd
jbdb
jdbb

abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

Chương trình sinh hoán vị kế tiếp của tập n phần tử có lặp.

#include <cstdio>
#include <iostream>
#include<string.h>
using namespace std;
char str[11];
int n;
void toPermutation(){
          while(true){
                    //print out.
                    for(int index = 0;index <n; index++){
                              cout<<str[index];
                    }
                    cout<<"\n";
                    // find j that arr[j] < arr[j+1]
                    int j = n -2;
                    while(j>=0 && str[j] >= str[j+1]){
                              j--;
                    }
                    if(j == -1) break;
                    // find index on the right that is minimum and greater than arr[j].
                    int minRightIndex = j+1;
                    for(int k=j+2;k<n;k++){
                              if(str[k] <= str[minRightIndex] && str[k] > str[j]){
                                        minRightIndex = k;
                              }
                    }
                    // wrap j and minRightIndex
                    char temp = str[j];
                    str[j] = str[minRightIndex];
                    str[minRightIndex] = temp;
                    //revert arr from j+1 to n
                    for(int loop = 0; loop < (n -1 -j)/2;loop++){
                              char temp = str[j +1 + loop];
                              str[j+1+loop] = str[n- 1 -loop];
                              str[n -1 -loop] = temp;
                    }
                   
          }
}
int main(int argc, char** argv)
{
          int tc, T;
          freopen("PERMUTATION.INP", "r", stdin);
          freopen("PERMUTATION.OUT", "w", stdout);
          cin >> T;
          for(tc = 0; tc < T; tc++)
          {
                    cin>>str;
                    n = strlen(str);
                    for(int i=0;i<n-1;i++){
                              for(int j=i+1;j<n;j++){
                                        if(str[i] > str[j]){
                                                  char temp = str[i];
                                                  str[i] = str[j];
                                                  str[j] = temp;
                                        }
                              }
                    }
                    toPermutation();
        cout<<"\n";
                    // Print the answer to standard output(screen).
                   
          }
          return 0;//Your program should return 0 on normal termination.

}

[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