【算法】全排列（有重复元素情况）的递归实现

分治递归想法： 能否将“多个元素的全排列 ”变成数个“较少元素的全排列 ”，分别进行？？？

所以 当面对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;
}