High school mathematics teaches about permutations and combinations, and sometimes all the "permutation" methods are listed. Now I'll help the teacher with that!
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The input contains multiple test cases, each on a separate line, consisting of a single positive integer N (1 <= N <= 7) representing the number of items to be arranged.The identifiers for the N items are represented by letters from 'a' to 'g'. When N = 0, it indicates the end of input (in this case should not be output). | For each set of data, output all permutations, with each permutation on a separate line. Permutations should be output in lexicographical order. |
| 2 3 0 | ab ba abc acb bac bca cab cba |
Thought Process
Use DFS and string concatenation to accumulate the answer. Run a for loop and declare a Map to store the currently visited letters. If the current letter has not been visited yet, increment Map[letter] and concatenate the letter to the string. Then call DFS again. After the call, remember to restore the Map and the string.
Sample Code－ZeroJudge I646: Permutations and Sorting
#include <iostream>
#include <map>
#include <vector>
using namespace std;
vector<string>ans;
int N;
void DFS(string str, map<char, int>MAP) {
if (str.length() == N) {
ans.push_back(str);
return;
}
for (int i = 0; i<N; i++) {
char ch = i + 'a';
if (MAP[ch] == 0) {
MAP[ch]++;
DFS(str+ch, MAP);
MAP[ch]--;
}
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
while (cin >> N && N != 0) {
ans.clear();
map<char, int>MAP;
DFS("", MAP);
for (int i = 0; i<ans.size(); i++) {
cout << ans[i] << "\n";
}
}
}
//ZeroJudge I646
//Dr. SeanXD