2014-02-05 21:12

题目描述：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入：

每个测试案例包括1行。

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

输出：

对应每组数据,按字典序输出所有排列。

样例输入：

abcBCA

样例输出：

abcacbbacbcacabcbaABCACBBACBCACABCBA

题意分析： 　　给定一个字符串，输出有其中的字母所能构成的全部排列。 　　首先，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 
     
       4 #include 
      
        5 #include 
       
         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 }