【算法】全排列（有重复元素情况）的递归实现
分治递归想法： 能否将“多个元素的全排列 ”变成数个“较少元素的全排列 ”，分别进行？？？
所以 当面对n个问题全排列时，考虑能否先确定首个位置的元素，然后对接下来的n-1个元素再进行全排列操作；接下来对n-1个元素，同样的思想，确定首位，然后接下来继续 ....... 直到最后只剩下一个元素，则该序***定，之后通过对每一次确定的元素进行依次变换，从而确定一个又一个序列。
R的全排列可归纳递归定义如下：
全排列的递归实现算法。
输入：先输入要求输入的字符的个数，后依次输入（或随机生成）每个字符（不能仅仅是数字）。
输出：全排列的结果。
示例：输入：3 / * 2，输出：/ * 2 / 2 * * / 2 * 2 / 2 * / 2 / *
源码：
需要考虑是否有重复元素，有则需要排除干扰项。故引入下面 isSwap（）函数
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
void swap(char *a,char *b)//进行交换操作，注意需要用到指针
{
char *temp;
temp=a;
a=b;
b=temp;
}
bool isSwap(char s[], int k, int m)//因为期间会有重复的元素出现，所以需要对重复元素进行判断，并将开头和结尾标记移动到不重复元素处
{
for(int i=k;i<m;i++) if(s[m]==s[i])return false;
return true;
}
void Perm(char s[], int k, int m)
{
if(k==m)//当序列开头=结尾时，即只剩一个元素时，直接输出序列
{
cout<<s<<endl;
}
else
{
for(int i=k;i<=m;i++)
{
if(isSwap(s,k,i))
{
swap(s[k],s[i]);
Perm(s,k+1,m);
swap(s[k],s[i]);
}
}
}
}
int main()
{
char s[N];
scanf("%s",s);
printf("%s的全排列是： \n",s);
int len=strlen(s);
Perm(s,0,len-1);//输入序列，以及头和尾
return 0;
}
投递曼伦商贸等公司6个岗位 >
