หา Permutation ที่ n-th แบบ Lexicographical ของสตริงใน C++

แนวคิด

กำหนดสตริงความยาว m ประกอบตัวอักษรพิมพ์เล็ก בלבד หา permutation ที่ n-th แบบ lexicographical (เรียงตามพจนานุกรม)

ตัวอย่างที่ 1

Input: str[] = "pqr", n = 3
Output: "qpr"
คำอธิบาย: Permutation ทั้งหมดเรียงแล้ว: pqr, prq, qpr, qrp, rpq, rqp

ตัวอย่างที่ 2

Input: str[] = "xyx", n = 2
Output: "xyx"
คำอธิบาย: Permutation ทั้งหมด: xxy, xyx, yxx

หลักการคำนวณ

• Permutation ของ N ตัวอักษรที่ต่างกันหมด = N!
• Permutation ของ N ตัวอักษรที่มีตัวซ้ำ (C1 ซ้ำ M1 ครั้ง, C2 ซ้ำ M2 ครั้ง...) = N! / (M1! × M2! × ... × Mk!)
• หลังจาก fix ตัวอักษรตัวแรก จำนวน permutation ที่เหลือ = (N-1)! / (ผลคูณ factorial ของความถี่ที่เหลือ)

ขั้นตอน

1. นับความถี่ตัวอักษรใน freq[]
2. จากตัวอักษรเล็กสุดที่ยังมีอยู่ (freq[i] > 0) คำนวณจำนวน permutation สูงสุดถ้า fix ตัวนั้นไว้หน้า
3. ถ้าผลรวม ≥ n → fix ตัวอักษรนั้น, ลด freq[i], ลด n, ทำต่อตัวถัดไป
4. ถ้าผลรวม < n → ลองตัวอักษรถัดไป ปรับ n ใหม่ จนกว่าจะเจอตัวที่ทำให้ผลรวม ≥ n

Time Complexity: O(n) โดย n = ความยาวสตริง

โค้ดตัวอย่าง

#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;
}

ผลลัพธ์

aiilnooprtsttu