a469: 10063 - Knuth's Permutation

2021-07-05 23:37:14 +0800 CST Tags: permutation

出處：https://zerojudge.tw/ShowProblem?problemid=a469
提交：https://zerojudge.tw/Submissions?problemid=a469&account=allllllan123456

問題：給你一個長度不超過 10 的字串，請你輸出該字串的字元排列按照 Knuth’s Permutation 方法所產生出的所有可能排列。對一個已經存在的排列：$A_1A_2A_3\ldots A_{n-1}$，要插入字元 $X$，所有可能的插入方式便為：$XA_1A_2A_3\ldots A_{n-1}$，$A_1XA_2A_3\ldots A_{n-1}$，$A_1A_2X$ $A_3\ldots A_{n-1}$，⋯，$A_1A_2A_3\ldots XA_{n-1}$，$A_1A_2A_3,\ldots A_{n-1}X$，總共 $n$ 種。於是要產生出所有的排列，只要從空字串開始，持續地按此要領依序插入第一個字元、第二個字元，⋯，直到最後一個字元即可。舉例來說，abc 的 Knuth’s Permutation 過程即為下面的樹狀圖，方法數為 $1\times 2\times 3$ 總共 6 種，由上至下依序輸出就是答案。

解法：原本的題目敘述只有提到說產生排列的程序是遞迴的，並給三組範例測資而已，並沒有如本篇的題目敘述一般直接揭露如何產生出所有的排列，我猜是因為這就是它的考點吧。

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4string str;
 5
 6void dfs(int index, string current) {
 7    if (index == str.length()) { cout << current << '\n'; return; }
 8    for (int i=0; i<=current.size(); i++)
 9        current.insert(i, string{str[index]}),
10        dfs(index+1, current),
11        current.erase(i, 1);
12}
13
14int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
15    while (cin >> str)
16        dfs(0, ""), cout << '\n';
17    return 0;
18}