[Series] Thuật toán Sinh | Kì hai: Sinh hoán vị

Mục lục

---

Giới thiệu
Giới thiệu thuật toán
Thuật toán khác

Giới thiệu

---

Một hoán vị trong toán học là một dãy gồm $n$ kí tự với các kí tự từ 1…9 xuất hiện duy nhất và chỉ một lần: 123, 321, 1234, …

Giới thiệu thuật toán

---

Thuật toán sinh hoán vị kế tiếp là một thuật toán được dùng trong tin học máy tính rất nhiều, và thường được thấy ở một số bài toán giải thuật áp dụng.
Giống với “Sinh Nhị Phân”, sinh hoán vị cũng là thuật toán được áp dụng với các bài toán mang tính “Lựa chọn” có thứ tự.
Ví dụ: Các cách sắp xếp các số từ 1 đến 3 có thể là: 123, 321, 132, 231, 213, 312

Thuật toán được phát biểu như sau:

• Từ phải qua trái tìm chỉ số đầu tiên xuất hiện trước dãy giảm dần:
  • Ví dụ: 6543721 thì vị trí cần tìm là i = 4 với A[i] = 3
• Trong đoạn giảm dần ở vị trí có phần tử nhỏ nhất vẫn lớn hơn A[i]:
  • Như trên thì chỉ só cần tìm là j = 5 A[j] = 7
• Đổi chỗ A[i] và A[j]
• Sau đó đảo ngược đoạn từ i + 1 -> cuối dãy

Code:

#include <iostream>
using namespace std;
int a[20], n;
void Init() {
 cin>>n;
 for (int i = 1; i <= n; i++)
  a[i] = i;
}
void InDay() {
 for (int i = 1; i <= n; i++)
  cout << a[i];
 cout<<endl;
}
void Swap(int &a, int &b) {
 int tmp = a;
 a = b;
 b = tmp;
}
void Sinh() {
 while(1) {
  InDay();
  int i = n - 1;
  while(i > 0 && a[i] > a[i + 1]) {
   i--;
  }
  if (i < 1) {
   break;
  }
  int k = n;
  while(k > i && a[k] < a[i]) {
   k--;
  }
  Swap(a[i], a[k]);
  int ptr1 = i + 1, ptr2 = n;
  while(ptr1 <= ptr2) {
   Swap(a[ptr1], a[ptr2]);
   ptr1++;
   ptr2--;
  }
 }
}
int main() {
 Init();
 Sinh();
}

Thuật toán khác

---

Bên cạnh việc sinh hoán vị bằng pp bên trên thì chúng ta cũng có thể sinh hoán vị bằng cách dùng pp Quay Lui được trình bày ở các bài trước.
Chúng ta sẽ dùng một mảng A[n+1] lưu các hoán vị, khi đó các hoán vị sẽ được biểu diễn như sau:
A[1], A[2], A[3], …,A[n].
Trong đó A[i] ≠ A[j] Với mọi i,j ∈ [1,n] và i ≠ j.
Để xác nhận một phần tử chỉ được dùng một lần ta sẽ dùng mảng Bool để lưu đánh dấu. Nếu phần tử chưa sử dụng thì sẽ có giá trị là 0 ngược lại sẽ có giá trị là 1. Ban đầu ta khởi tạo tất cả các phần tử trong mảng đều có giá trị là 0.
Ý tưởng của phương pháp quay lui là chúng ta sẽ chọn ra một phần tử chưa sử dụng. Lưu phần tử đó vào một cấu hình tổ hợp, sau đó đánh dấu nó đã sử dụng. Ta sẽ lặp lại công việc như trên đến khi đủ cấu hình cho một tổ hợp thì sẽ xuất ra màn hình. Sau khi xuất ra ta lại quay trở lại bước trước đó để đánh dấu là nó chưa được chọn.
Ta có thể hình dung bài toán như hình vẽ sau: Với n=3 thì bài toán trở thành liệt kê các hoán vị của các phần tử 1, 2, 3. Các hoán vị được liệt kê theo thứ tự từ điển tăng dần như hình vẽ sau:

Code:

#include <iostream>
using namespace std;
int a[20], n, danhdau[20] = {};
void Init() {
 cin>>n;
 for (int i = 1; i <= n; i++)
  a[i] = i;
}
void InDay() {
 for (int i = 1; i <= n; i++)
  cout << a[i];
 cout<<endl;
}
void Swap(int &a, int &b) {
 int tmp = a;
 a = b;
 b = tmp;
}
void Try(int i) {
 for (int j = 1; j <= n; j++) {
  if (danhdau[j] == 0) {
   danhdau[j] = 1;
   a[i] = j;
   if (i == n) {
    InDay();
   } else {
    Try(i + 1);
   }
   danhdau[j] = 0;
  }
 }
}
int main() {
 Init();
 Try(1);
}

Khi chúng ta dùng sinh hoán vị bằng pp sinh kế tiếp ta có thể bắt đầu từ bất kì cấu hình nào. Còn dùng sinh hoán vị theo pp Quay lui nhất định ta phải bắt đầu từ cấu hình đầu tiên là 1…n

Bài tập luyện tập:
https://www.spoj.com/PTIT/problems/BCPERMU/
https://www.spoj.com/PTIT/problems/BCNEPER/