递归方式
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| #include <cstdio> #include <iostream> #include <algorithm> #include <string> using namespace std; const int MAXN = 10;
bool visit[MAXN]; char sequence[MAXN];
void GetPermutation(string str, int index){ if (index == str.size()) { for (int i = 0; i < str.size(); ++i) { putchar(sequence[i]); } printf("\n"); } for (int i = 0; i < str.size(); ++i) { if (visit[i]) { continue; } else { visit[i] = true; sequence[index] = str[i]; GetPermutation(str, index + 1); visit[i] = false; } } } int main(){ string str; while (cin >> str) { sort(str.begin(), str.end()); GetPermutation(str, 0); printf("\n"); } return 0; }
|
非递归方式
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| #include <cstdio> #include <iostream> #include <algorithm> #include <string> using namespace std;
bool GetNextPermutation(string &str){ int n = str.size(); int index = n - 2; while (index >= 0 && str[index] >= str[index + 1]) { index--; } if (index < 0) { return false; } for (int i = n - 1; i > index; --i) { if (str[i] > str[index]) { swap(str[index], str[i]); break; } } reverse(str.begin() + index + 1, str.end()); return true; } int main(){ string str; while (cin >> str) { sort(str.begin(), str.end()); do { cout << str << endl; } while (GetNextPermutation(str)); cout << endl; }
return 0; }
|
使用系统函数
next_permutation()
和非递归方式求全排列的用法一样,是计算当前序列的下一个序列,该函数位于algorithm
头文件中。
它有三个参数:
- 序列的首地址
- 序列的尾地址
- 比较函数(可选),默认是字典序排列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| #include <iostream> #include <algorithm> #include <string> using namespace std;
int main(){ string str; while (cin >> str) { sort(str.begin(), str.end()); do { cout << str << endl; } while (next_permutation(str.begin(), str.end())); cout << endl; }
return 0; }
|
__END__