字符串的排列

/***************************************************************
题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入
字符串abc，则打印出由a、b、c所能排列出来的所有字符串abc、acb、
bac、cab和cba。
***************************************************************/
#include<stdio.h>

void stringPermutation(char* pStr, char* pBegin);
void stringPermutation(char* pStr)
{
	if(pStr == NULL)
		return;

	stringPermutation(pStr,pStr);
}
void stringPermutation(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;

			stringPermutation(pStr,pBegin+1);

			temp = *pCh;	//将子字符串第一个字符交换回来
			*pCh = *pBegin;
			*pBegin = temp;
		}
	}
}

void test()
{
	char pStr[] = "abc";	//注意这里不能写成char* pStr = "abc";
	stringPermutation(pStr);
}
int main()
{
	test();
	return 0;
}

相关题目：


1.输入一些字符，求这些字符的所有组合。比如输入a,b,c，则它们的组合有
a,b,c,ab,ac,bc,abc。
解题思路：
如果输入n个字符，则这n个字符能构成长度为1的组合、长度为2的组合.....
长度为n的组合。在求n个字符的长度为m(1<=m<=n)的组合的时候，我们把这n
个字符分成两部分：第一个字符和其余的所有字符。如果组合包含第一个字符，
则下一步在剩余的字符里选取m-1个字符；如果组合里不包含第一个字符，则下
一步在剩余的n-1个字符里选取m个字符。也就是说，我们可以把求n个字符组成
长度为m的组合问题分解成了两个子问题，分别求n-1个字符串中长度为m-1的组合，
以及求n-1个字符的长度为m的组合。这两个子问题都可以用递归的方式解决。


2.输入一个含有8个数字的数组，判断有没有可能把这8个数字分别放到正方体
的8个定点上，使得正方体上三组相对的面上的4个顶点的和都相等。
解题思路：
这相当于先得到a1,a2,a3,a4,a5,a6,a7,a8这八个数字的所有排列，然后判断
有没有某一个排列符合题目给定的条件，即s2+a2+a3+a4=a5+a6+a7+a8,
a1+a3+a5+a7=a2+a4+a6+a8,并且a1+a2+a5+a6=a3+a4+a7+a8.


3.在8*8的国际象棋上摆放8个皇后，使其不能相互攻击，即任意两个皇后不得
处在同一行、同一列或者同一对角线上。请问总共有多少种符合条件的摆法。
解题思路：
由于8个皇后的任意两个不能处在同一行，那么肯定是每一个皇后占据一行。
于是我们可以定义一个数组ColumnIndex[8],数组中第i个数字表示位于第i行
的皇后的列号。先把数组ColumnIndex的8个数字分别用0~7初始化，接下来就是
对数组ColumnIndex做全排列。因为我们是用不同的数字初始化数组，所以任意
两个皇后肯定不同列。我们只需要判断每一个排列对应的8个皇后是不是在同一
对角线上，也就是对于数组的两个下标i和j,是不是i-j=ColumnIndex[i]-ColumIndex[j]
或者j-i=ColumnIndex[i]-ColumnIndex[j]。


相关题目1的答案

void AllSubstring3(const char *str,char *arr)
{
	//传入的arr的长度为len+1，最后一个位置保存'\0'
	int i,j;
	unsigned int len = strlen(str);
	strcpy(arr,str);
	for(i=len-1;i>=0;i--)
	{
		arr[i+1] = '\0';
		for(j=i;j>=0;j--)
			printf("%s\t",&arr[j]);
		printf("\n");
	}
}

总结：
如果面试题是按照一定要求摆放若干个数字，我们可以先求出这些数字
的所有排列，然后再一一判断每个排列是不是满足题目给定的要求。

==参考剑指offer 和http://blog.csdn.net/ns_code/article/details/21043665