HDU 1027 Ignatius and the Princess II：字典序第 M 小排列的 DFS 生成

題目大意

給定 n 和 m，輸出 1~n 的全排列中字典序第 m 小的排列。n ≤ 10，m 不超過總排列數。

DFS + 計數器

遞歸生成全排列，按字典序（即從 1 到 n 選未用數字）。全局計數器 cnt，每生成一個完整排列 cnt++，當 cnt == m 時輸出並停止遞歸（返回 true 向上傳播終止）。

C++ 代碼

#include 
using namespace std;
const int MAXN = 15;
int ans[MAXN];
bool used[MAXN];
int n, m, cnt;

bool dfs(int pos) {
    if (pos > n) {
        if (++cnt == m) return true;
        return false;
    }
    for (int i = 1; i <= n; ++i) if (!used[i]) {
        used[i] = true;
        ans[pos] = i;
        if (dfs(pos + 1)) return true;
        used[i] = false;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n >> m) {
        memset(used, 0, sizeof(used));
        cnt = 0;
        dfs(1);
        for (int i = 1; i <= n; ++i) {
            if (i > 1) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

優化：康托展開 O(n²) 直接構造

若 n 較大（如 20），DFS 會 TLE。可用康托展開將 m-1 分解為階乘進制，直接確定每位選哪個剩餘數字。但本題 n ≤ 10，DFS 完全足夠。

關鍵點

• 遞歸終止條件：pos > n 表示排列完整，檢查計數器。
• 向上傳播 true 可立即停止所有遞歸，避免多餘計算。
• 輸出格式：數字間單空格，行末無多餘空格。

總結

HDU 1027 是「全排列生成 + 字典序定位」的入門題。DFS 回溯配合計數器是最直觀解法；掌握 康托展開 可解決大 n 版本。同類題：POJ 1833、LeetCode 60。