问题：给定一个字符串，输出字符串中所有字符的所有排列。如"abc"的全排列是：abc, acb, bac, bca, cab, cba。
引申问题：给定一个数字n，要求输出该数字1~n的全排列。如n=3的全排列是：123, 132, 231, 213, 312, 321。
问题分析：对于字符串的全排列问题可以才有交换的思想。举例说明：
1
2
3
4
5
6
7
8
9
10
11
12
|
void (string res, string str)
{
if(str.length() == 0)
cout<<res<<endl;
else
{
for(int i = 0; i < str.length(); i++)
{
strpermutation(res+str[i],str.substr(0,i)+str.substr(i+1,str.length()));
}
}
}
|
对于引申问题：采用DFS搜索算法实现。
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
|
#define LENGTH 10
int book[LENGTH] = {0};
int res[LENGTH] = {0};
void dfsNpermutation(int step)
{
if(step == n+1)
{
for(int i = 0;i < n;i++)
{
cout<<res[i];
}
cout<<endl;
return;
}
for(int i = 1; i <= n; i++)
{
if(book[i] == 0)
{
res[i] = i;
book[i] = 1;
dfsNpermutation(step+1);
book[i] = 0;
}
}
return;
}
|
近期评论