permutations全排列的递归算法（c++实现）

算法实现原理： 假如abc排列组合会得到abc,acb,bac,bca,cab,cba六种情况。 1）首先将abc的第一个字母放到三者中的第一位得到abc，接着剩下两个字母bc，可以将bc中的第一个字母放到两者中的第一位得到abc，也可以将bc中的第二个字母放到两者中的第一位得到acb。 2）将abc的第二个字母放到三者中的第一位得到bac，接着剩下两个字母ac，可以将ac中的第一个字母放到两者中的第一位得到bac，也可以将ac中的第二个字母放到两者中的第一位得到bca。 … 以此类推。

如果按以上的算法计算acc的排列组合，那么会得到acc,acc,cac,cca,cca,cac六种情况。 那么需要排除其中重复的情况。

对重复的元素序列进行排列组合： 在交换并且进行递归的时候，需要判断交换的两者之间是否有与后者相同的数。比如在计算acc的排列组合时，将acc的第三个字母放到三者中的第一位与将acc的第二个字母放到三者中的第一位是重复的情况，那么则不需要将第三个字母放到第一位进行排列。

代码实现：

#include <iostream>
using namespace std;
void perm(char*, const int, const int);
bool isHaveSame(char*, const int, const int);
int main()
{
	char list[10];
	cin >> list; //当输入abc时
	perm(list, 0, strlen(list)-1); //  strlen(list)-1==2
	return 0;
}
void perm(char* x, const int start, const int end)//核心函数
{
	if (start == end)//当运算到最后一位时则表示这种情况排列完成，输出其结果
	{
		for (int i = 0; i <= end; i++)
			cout << x[i];
		cout << endl;
	}
	else
	{
		for (int i = start; i <= end; i++)
		{
			if (isHaveSame(x,start,i))//如果start与i之间没有重复的话，进行排列
			{
				swap(x[start], x[i]);//先将第i位放到start位置
				perm(x, start + 1, end);//将除去一位的字母串进行递归排列
				swap(x[start], x[i]);//排列完再将其交换回来
			}
		}
	}
}
bool isHaveSame(char* x, const int start, const int end)//判断在star-end之间是否有重复的元素
{
	for (int i = start; i < end; i++)
	{
		if (x[i] == x[end])//如果有则为0
			return 0;
	}
	return 1;//如果没有则为1
}