字符串的排列组合

题目描述： 
输入一个字符串，打印出该字符串中字符的所有排列。 
基本思路： 
从字符串中选出一个字符作为排列的第一个字符，然后对剩余的字符进行全排列，如此递归，从而得到所有字符的全排列。以对字符”abc”进行全排列为例，可以按下述步骤执行： 
将a固定在第一位，求后面bc的排列 
将b固定在第一位，求后面ac的排列 
将c固定在第一位，求后面ab的排列

#include #include #define swap(t,x,y) (t = (x),x = (y),y = (t)) void CalcAllPermutation(char *perm,int from,int to)
{ if (to < 0) return ; int i = 0; char t; if (from == to)
    { for (i = 0;i <= to;i++)
            printf("%c",perm[i]);
        printf("\n");
    } else { for (i = from;i <= to;i++)
        {
            swap(t,perm[i],perm[from]);//将from-to中的一个元素固定在第一位 CalcAllPermutation(perm,from+1,to);
            swap(t,perm[i],perm[from]);//恢复以前的状态 }
    }
} int main()
{ char s[] = "abcd";
    CalcAllPermutation(s,0,3); return 0;
} 

	
	

		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
	

	

		31
	

	

		32
	

运行结果(centos5.5) 
[root@localhost ~]# ./a.out 
abcd 
abdc 
acbd 
acdb 
adcb 
adbc 
bacd 
badc 
bcad 
bcda 
bdca 
bdac 
cbad 
cbda 
cabd 
cadb 
cdab 
cdba 
dbca 
dbac 
dcba 
dcab 
dacb 
dabc 
题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。 
上面我们详细讨论了如何用递归的思路求字符串的排列。同样，本题也可以用递归的思路来求字符串的组合。
假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：第一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；第二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码：

 #include #include #include using namespace std; #include void Combination(char *string ,int number,vector<char> &result); void Combination(char *string)
{
    assert(string != NULL); vector<char> result; int i , length = strlen(string); for(i = 1 ; i <= length ; ++i)
        Combination(string , i ,result);
} void Combination(char *string ,int number , vector<char> &result)
{
    assert(string != NULL); if(number == 0)
    { static int num = 1; printf("第%d个组合\t",num++); vector<char>::iterator iter = result.begin(); for( ; iter != result.end() ; ++iter) printf("%c",*iter); printf("\n"); return ;
    } if(*string == '\0') return ;
    result.push_back(*string);
    Combination(string + 1 , number - 1 , result);
    result.pop_back();
    Combination(string + 1 , number , result);
} int main(void)
{ char str[] = "abc";
    Combination(str); return 0;
}

	
	

		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
	

	

		31
	

	

		32
	

	

		33
	

	

		34
	

	

		35
	

	

		36
	

	

		37
	

	

		38
	

	

		39
	

	

		40
	

	

		41
	

	

		42
	

	

		43
	

	

		44
	

	

		45
	

	

		46
	

运行结果如下：(centos5.5) 
[root@localhost ~]# ./a.out 
第1个组合 a 
第2个组合 b 
第3个组合 c 
第4个组合 ab 
第5个组合 ac 
第6个组合 bc 
第7个组合 abc