Tìm hoán vị thứ n theo thứ tự từ điển của chuỗi trong C++

Khái niệm

Cho chuỗi độ dài m chỉ chứa chữ cái thường. Tìm hoán vị thứ n theo thứ tự từ điển.

Ví dụ 1

Đầu vào: str = "pqr", n = 3

Đầu ra: "qpr"

Giải thích: Các hoán vị theo thứ tự: pqr, prq, qpr, qrp, rpq, rqp

Ví dụ 2

Đầu vào: str = "xyx", n = 2

Đầu ra: "xyx"

Giải thích: Các hoán vị: xxy, xyx, yxx

Phương pháp

Dùng toán học tổ hợp:

• Tổng hoán vị của N ký tự khác nhau: N!
• Nếu có ký tự trùng lặp (tần suất M1, M2...): N!/(M1! * M2! * ...)
• Sau khi cố định ký tự đầu, số hoán vị còn lại: (N-1)!/(...)

Các bước:

1. Đếm tần suất ký tự trong freq[].
2. Từ ký tự nhỏ nhất có freq > 0, tính số hoán vị tối đa nếu cố định ký tự đó làm đầu.
3. Nếu tổng >= n: chọn ký tự đó, giảm freq, tiếp tục với n-1 ký tự còn lại.
4. Nếu tổng < n: thử ký tự tiếp theo, cập nhật tổng cho đến khi tìm thấy.

Độ phức tạp O(độ dài chuỗi).

Ví dụ

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
const int MAX_CHAR1 = 26;
const int MAX_FACT1 = 20;
ll fact1[MAX_FACT1];

void precomputeFactorials() {
    fact1[0] = 1;
    for (int i = 1; i < MAX_FACT1; i++)
        fact1[i] = fact1[i - 1] * i;
}

void nPermute(char str1[], int n1) {
    precomputeFactorials();
    int len1 = strlen(str1);
    int freq1[MAX_CHAR1] = {0};
    for (int i = 0; i < len1; i++)
        freq1[str1[i] - 'a']++;
    char out1[MAX_CHAR1];
    int sum1 = 0, k1 = 0;
    while (sum1 != n1) {
        sum1 = 0;
        for (int i = 0; i < MAX_CHAR1; i++) {
            if (freq1[i] == 0) continue;
            freq1[i]--;
            int xsum1 = fact1[len1 - 1 - k1];
            for (int j = 0; j < MAX_CHAR1; j++)
                xsum1 /= fact1[freq1[j]];
            sum1 += xsum1;
            if (sum1 >= n1) {
                out1[k1++] = i + 'a';
                n1 -= (sum1 - xsum1);
                break;
            }
            if (sum1 < n1)
                freq1[i]++;
        }
    }
    for (int i = MAX_CHAR1 - 1; k1 < len1 && i >= 0; i--)
        if (freq1[i]) {
            out1[k1++] = i + 'a';
            freq1[i]--;
        }
    out1[k1] = '\0';
    cout << out1;
}

int main() {
    int n1 = 5;
    char str1[] = "tutorialspoint";
    nPermute(str1, n1);
    return 0;
}

Đầu ra

aiilnooprtsttu