alan23273850 的刷題筆記
d436: 10098 - Generating Fast, Sorted Permutation
Tags: permutation
出處：https://zerojudge.tw/ShowProblem?problemid=d436
提交：https://zerojudge.tw/Submissions?problemid=d436&account=allllllan123456
問題：給你一個長度不超過 10 的字串，字串只會包含大小寫字母及數字 (字元可能重複)，請你按照 ASCII 碼的字典順序依序印出字串中的這些字元重新打散之後的所有排列，並且注意到如果當下的字串已經在之前就出現過的話則不予印出。
解法：這題與 d115 有所不同，因為重複字元會讓原本傳統的方式印出已經出現過的字串，為了避免這個問題，我們改統計每個字元出現的次數，並且仍然按照 ASCII 碼排序，只要對於每個位置都維持優先選 ASCII 小的字元，接下來才是 ASCII 大的字元，如果某個字元已經在前面的位置都用光了當然就沒辦法選，那每次全部的字母一用完就印出該字串，這樣就自然會是不重複的字典順序了。
1#include <bits/stdc++.h>
2using namespace std;
3
4int len;
5char arr[10], num[10];
6
7void dfs(string ans) {
8 bool allUsed = true;
9 for (int i=0; i<len; i++)
10 if (num[i]) allUsed = false,
11 num[i]--, dfs(ans + arr[i]), num[i]++;
12 if (allUsed) cout << ans << '\n';
13}
14
15int main() { ios_base::sync_with_stdio(false); cin.tie(0); // IO 優化
16 int T; cin >> T;
17 while (T--) { cin >> arr;
18 len = strlen(arr); memset(num, 0, sizeof num);
19 sort(arr, arr + len);
20 int j = 0; num[0] = 1;
21 for (int i=1; i<len; i++)
22 if (arr[i] == arr[j]) num[j]++;
23 else j++, arr[j] = arr[i], num[j] = 1;
24 arr[j+1] = 0;
25 dfs(""); cout << '\n';
26 }
27 return 0;
28}