【算法15】字符串的全排列

【题目】输入一个字符串，打印该字符串的所有排列。例如输入字符串abc，输出其全排列为abc，acb，bac，bca，cab，cba。

【思路】我们想一下，如果不编程，手工做的话，我们的基本考虑是：每次首先固定一个字母，然后让其余的字母全排列；然后换一个字母固定，再全排列其余的字母，如此循环而已。换句话说：假设长度为n的字符串排列方式是f(n)，那么我们的基本思路是：每次让n个字母中的一个字母“打头阵”，其余的n-1个字母则按f(n-1)的方式排列。这样我们就明白这明显是递归思路。

　　递归最重要的问题是：结束的条件是什么？或者说，最小子问题是什么？还是以上面的abc例子来说明，首先固定a，然后排列bc；排列bc成为一个子问题，同样固定b，排列c；排列c成为子问题，固定c，剩下一个字符串结束符('\0')；碰到结束符，前面的字符已经都排好了，所以我们只需要打印前面所有已经固定的字符就可以了。

　　根据这种思路，我们容易得到如下的代码：

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 
 5 void StringPermutation(char *str,char *perBegin)
 6 {
 7     if(str == NULL || perBegin == NULL)
 8         return;
 9 
10     //如果开始排列的位置为结束符，打印结束符前的所有字符
11     if(*perBegin == '\0')
12     {
13         cout<<str<<endl;
14     }
15     else
16     {
17     
18         for(char *pch = perBegin;*pch != '\0';++pch)
19         {
20             //交换第n个字符与第一个字符的位置
21             char temp = *pch;
22             *pch = *perBegin;
23             *perBegin = temp;
24 
25             //排列第一个字符后的所有字符
26             StringPermutation(str,perBegin + 1);
27 
28             //将第n个字符再与第一个字符交换过来
29             temp = *pch;
30             *pch = *perBegin;
31             *perBegin = temp;
32         }
33     }
34 }
35 
36 void StringPermutation(char *string)
37 {
38     StringPermutation(string,string);
39 }
40 
41 int main()
42 {
43     char p[] = "abc";
44 
45     StringPermutation(p);
46     
47     return 0;
48 }

　　运行结果如下：

【算法15】字符串的全排列

【思路2】当然如果我们知道C++的库函数next_permutation，那么就不用这么麻烦了，因为库函数的算法都是封装的，所以没什么好说的，直接上代码：

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 
 5 void StringPermutation(char *str,char *perBegin)
 6 {
 7     if(str == NULL || perBegin == NULL)
 8         return;
 9 
10     //如果开始排列的位置为结束符，打印结束符前的所有字符
11     if(*perBegin == '\0')
12     {
13         cout<<str<<endl;
14     }
15     else
16     {
17     
18         for(char *pch = perBegin;*pch != '\0';++pch)
19         {
20             //交换第n个字符与第一个字符的位置
21             char temp = *pch;
22             *pch = *perBegin;
23             *perBegin = temp;
24 
25             //排列第一个字符后的所有字符
26             StringPermutation(str,perBegin + 1);
27 
28             //将第n个字符再与第一个字符交换过来
29             temp = *pch;
30             *pch = *perBegin;
31             *perBegin = temp;
32         }
33     }
34 }
35 
36 void StringPermutation(char *string)
37 {
38     StringPermutation(string,string);
39 }
40 
41 int main()
42 {
43     char p[] = "abc";
44 
45     StringPermutation(p);
46     
47     return 0;
48 }

　　运行结果如下：

【算法15】字符串的全排列

References:

【1】何海涛博客：http://zhedahht.blog.163.com/blog/static/254111742007499363479/

【2】标准库全排列：http://hi.baidu.com/%D6%D5%BD%E1%D5%DF192/blog/item/a8ce8d23753d1eb64723e800.html

注：

1）本博客所有的代码环境编译均为win7+VC6。所有代码均经过博主上机调试。

2）博主python27对本博客文章享有版权，网络转载请注明出处http://www.cnblogs.com/python27/。对解题思路有任何建议，欢迎在评论中告知。

秒客网

【算法15】字符串的全排列

相关文章