Sinh theo thứ tự từ điển

Giả sử đang có hoán vị \((A_1, A_2, ... , A_N)\) , sinh hoán vị tiếp theo trong thứ tự từ điển bằng thuật toán sau:

Bước 1: Tìm vị trí \(K\) lớn nhất thoả \(A_K < A_{K+1}\), nếu không tìm được thì đây là hoán vị cuối cùng, dừng thuật toán.
Bước 2: Tìm vị trí \(L\) lớn nhất thoả \(A_K < A_L\)
Bước 3: Đổi chỗ 2 phần tử \(A_K\) và \(A_L\).
Bước 4: Đảo ngược mảng trong đoạn \((A_{K+1}, A_{K+2},..., A_N)\).

Lặp lại các bước trên đến khi sinh được hoán vị cuối cùng.

#include <iostream>
#include <vector>
using namespace std;

void print(const vector<int> &a) {
    for (int i=0; i<a.size(); i++) cout << a[i] << " ";
    cout << endl;
}

void permute(vector<int> &a, int n) {
    while (true) {
        print(a);
        int k, l;
        for (k = n-2; k>=0; k--) if (a[k] < a[k+1]) break; // Bước 1
        if (k<0) break;                                    //
        for (l = n-1; l>k; l--) if (a[k] < a[l]) break; // Bước 2
        swap(a[k], a[l]); // Bước 3
        for (int i=k+1, j=n-1; i<j; i++, j--) swap(a[i], a[j]); // Bước 4
    }
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5, 6, 7};
    permute(a, a.size());
    return 0;
}

Sinh theo thuật toán Heap (Heap’s Algorithm)

Hoán vị sinh theo thuật toán Heap thoả mãn: hoán vị sau được tạo thành từ hoán vị trước bằng cách hoán vị 2 phần tử, các phần tử khác giữ nguyên vị trí.

Cài đặt đệ quy:

void permute(vector<int> &a, int k) {
    if (k==1) return print(a);
    for (int i=0; i<k-1; i++) {
        permute(a, k-1);
        if (k%2==0) swap(a[i], a[k-1])
        else swap(a[0], a[k-1]);
    }
    permute(a, k-1);
}

Cài đặt không đệ quy:

void permute(vector<int> &a, int n) {
    vector<int> c(0, n);
    print(a, n);
    int i=0;
    while (i<n) {
        if (c[i] < i) {
            if (i%2 == 0) swap(a[0], a[i])
            else swap(a[c[i]], a[i]);
            print(a, n);
            c[i]++;
            i = 0;
        } else c[i++] = 0;
    }
}

Sinh theo thứ tự từ điển

Sinh theo thuật toán Heap (Heap’s Algorithm)

Xem thêm