剑指Offer - 九度1369 - 字符串的排列
2014-02-05 21:12

题意分析：
　　给定一个字符串，输出有其中的字母所能构成的全部排列。
　　首先，STL的algorithm中提供了next_permutation函数来输出下一个排列，所以你可以偷懒用用，当然也可以自己写一个。
　　于是乎，我自己写了一个，并且返回值为false时表示此排列已经是降序排列了，也就是说：没有比这“更大的”的排列了，这里的“大”指的是字典序。
　　时间复杂度为O(n!*n)，其中n!表示最多有n!个排列，n表示每次生成下一个排列需要O(n)的时间复杂度。空间复杂度是O(1)。

 1 // 688144    zhuli19901106    1369    Accepted    点击此处查看所有case的执行结果    1020KB    1032B    60MS
 2 // 201401311639
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <cstring>
 6 using namespace std;
 7 
 8 void my_swap(char &x, char &y)
 9 {
10     char ch;
11 
12     ch = x;
13     x = y;
14     y = ch;
15 }
16 
17 void my_reverse(char s[], int ll, int rr)
18 {
19     if (ll >= rr) {
20         return;
21     }
22 
23     int i;
24     for (i = ll; i < ll + rr - i; ++i) {
25         my_swap(s[i], s[ll + rr - i]);
26     }
27 }
28 
29 bool my_next_permutation(char s[], int n)
30 {
31     int i, j;
32 
33     for (i = n - 1; i > 0; --i) {
34         if (s[i - 1] < s[i]) {
35             break;
36         }
37     }
38     if (i == 0) {
39         return false;
40     }
41     --i;
42 
43     for (j = n - 1; j > i; --j) {
44         if (s[i] < s[j]) {
45             my_swap(s[i], s[j]);
46             break;
47         }
48     }
49     my_reverse(s, i + 1, n - 1);
50 
51     return true;
52 }
53 
54 int main()
55 {
56     char s[20];
57     int n;
58 
59     while (scanf("%s", s) == 1) {
60         n = strlen(s);
61         sort(s, s + n);
62         while (true) {
63             puts(s);
64             if(!my_next_permutation(s, n)) {
65                 break;
66             }
67         }
68     }
69 
70     return 0;
71 }