🔗 UVA-941 Permutations

tags: `數學(Math)` `遞迴(Recursion)` `回溯(Backtracking)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定一個字串 $S$ 和一個整數 $N$ ，找到字串 $S$ 的所有排列中的第 $N+1$ 個最小元素（按照字典序）。這些排列是對字串的所有可能組合，並且按照字典序排序。

注意，給定的 $S$ 可能沒有事先排序。

約束

$1 \leq |S| \leq 20$
$1 \leq N + 1 \leq 20!$

思路：數學(Math) + 縮小問題範圍

由於 $S \leq 20$ ，而 $20! = 2432902008176640000$ ，顯然生成所有排列不是一個好方法。因此應該使用數學方法計算排列的位置，而不是生成所有排列。

舉個🌰，假設 $S = \rm{"abcde"}$ 、 $N = 15$ ，改成用 $0\rm{-indexed}$ 表示。

由於需要按照字典序排序，故前 $[0, 23]$ 個排列的第 $1$ 個元素都是 $a$ ；前 $[24, 47]$ 個排列的第 $1$ 個元素都是 $b$ ，以此類推。而在確定了第一個元素後，也能按照相同的方法繼續確定之後的元素，但後續就不用考慮已經確定的字元。
確定答案的第 $1$ 個元素為 $\rm{"a"}$ 後，剩餘的元素為 $\rm{"bcde"}$ 。且 $N = 15 \mod 4! = 15$ ，故接下來是找到在 $\rm{"bcde"}$ 的排列中的第 $15$ 個排列。
在 $\rm{"bcde"}$ 的排列中，前 $[0, 5]$ 個排列的第 $1$ 個元素都是 $b$ ；前 $[6, 11]$ 個排列的第 $1$ 個元素都是 $c$ ；前 $[12, 17]$ 個排列的第 $1$ 個元素都是 $d$ ；前 $[18, 23]$ 個排列的第 $1$ 個元素都是 $e$ 。由於 $N = 15$ ，因此答案的第 $2$ 個元素是 $d$ ，剩餘的元素為 $\rm{"bce"}$ 。且 $N = 15 \mod 3! = 3$ ，故接下來是找到在 $\rm{"bce"}$ 的排列中的第 $3$ 個排列。
在 $\rm{"bce"}$ 的排列中，前 $[0, 1]$ 個排列的第 $1$ 個元素都是 $b$ ；前 $[2, 3]$ 個排列的第 $1$ 個元素都是 $c$ ；前 $[4, 5]$ 個排列的第 $1$ 個元素都是 $e$ 。由於 $N = 3$ ，因此答案的第 $3$ 個元素是 $c$ ，剩餘的元素為 $\rm{"be"}$ 。且 $N = 3 \mod 2! = 1$ ，故接下來是找到在 $\rm{"be"}$ 的排列中的第 $1$ 個排列。
在 $\rm{"be"}$ 的排列中，前 $[0, 0]$ 個排列的第 $1$ 個元素都是 $b$ ；前 $[1, 1]$ 個排列的第 $1$ 個元素都是 $e$ 。由於 $N = 1$ ，因此答案的第 $4$ 個元素是 $e$ ，剩餘的元素為 $\rm{"b"}$ 。且 $N = 1 \mod 1! = 0$ 。
由於只剩下一個元素，故答案的第 $5$ 個元素是 $b$ 。答案為 $\rm{"adceb"}$ 。

理解上述範例後，可以將其拆解成以下步驟：

將 $S$ 排序
逐位確定每個元素，由於相同字元不能重複使用，因此每次確定一個元素後，要將其從 $S$ $S$ 中刪除
- 透過計算階乘來計算每個元素的位置
- 透過取餘數來計算下一個元素的位置
重複步驟 $2$ 直到 $S$ 為空

複雜度分析

時間複雜度： $\mathcal{O}(m^2)$ $O (m^{2})$ ，其中 $m$ $m$ 為 $S$ $S$ 的長度。
- 計算 $\rm{factorial}$ 的時間複雜度為 $\mathcal{O}(m)$ 。
- 排序 $S$ 的時間複雜度為 $\mathcal{O}(m \log m)$ 。
- 每次確定元素時，需要刪除被確定的元素，需要 $\mathcal{O}(m)$ 的時間，因此總共的時間複雜度為 $\mathcal{O}(m^2)$ 。
空間複雜度： $\mathcal{O}(m)$

from math import factorial

t = int(input())

for _ in range(t):
    s = sorted(input()) # 記得排序
    n = int(input())

    ans = ""
    while len(s) > 0:
        x = factorial(len(s)-1)
        i = n // x # 回溯法要逐個確定，但其實可以直接計算
        ans += s[i]
        s = s[:i] + s[i+1:] # 刪除已經用過的字元
        n %= x
    print(ans)

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 20;
#define endl '\n'

LL fact[N]; // 預處理 N! 的值

void init() {
    fact[0] = 1;
    for (int i=1; i<N; i++) {
        fact[i] = fact[i-1] * i;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    LL t, n, x, i;
    cin >> t;
    init();
    string s, ans;
    while (t--) {
        cin >> s >> n;
        ans = "";
        sort(s.begin(), s.end());
        while (s.size() > 0) {
            x = fact[s.size()-1];
            i = n / x;
            ans += s[i];
            s.erase(i, 1);
            n %= x;
        }
        cout << ans << endl;
    }
    return 0;
}