更新时间:2022-08-12 23:27:07
题目:输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab、cba。 |
求整个字符串的排列,可以看成两步:
分析到这里,其实可以看出,这就是很典型的递归思路。
实现代码如下:
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
|
void Permutation( char * pStr)
{ if (pStr == NULL)
return ;
Permutation(pStr, pStr);
} void Permutation( char * pStr, char * pBegin)
{ if (*pBegin == '\0' )
{
printf ( "%s\n" , pStr);
}
else
{
for ( char * pCh = pBegin; *pCh != '\0' ; ++ pCh)
{
char temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
}
}
} |
在函数Permutation(char* pStr, char* pBegin)中,指针pStr指向整个字符串的第一个字符,pBegin指向当前我们做排列操作的字符串的第一个字符。在每一次递归的时候,我们从pBegin向后扫描每一个字符(即指针pCh指向的字符)。在交换pBegin和pCh指向的字符之后,我们再对pBegin后面的字符递归地做排列操作,直至pBegin指向字符串的末尾。
测试代码如下:
扩展1:如果不是求字符的所有排列,而是求字符的所有组合,应该怎么办呢?当输入的字符串中含有相同的字符串时,相同的字符交换位置是不同的排列,但是同一个组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc。(字符串的组合)
扩展2:输入一个含有8个数字的数组,判断有没有可能把这8个数字分别放到正方体的8个顶点上,使得正方体上三组相对的面上的4个顶点的和相等。
本文转自夏雪冬日博客园博客,原文链接:http://www.cnblogs.com/heyonggang/p/3405948.html,如需转载请自行联系原作者