Question

不重复的全排列问题，用递归实现。。。

这个方法很多，我比较容易理解递归的算法，但是我真不知道怎么去掉重复的排列，求大神赐教

最开始我错误的认为重复的就是相邻的 导致出现以下代码
**************************************************************************************************************

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 100
char *index; //保存上一个排列的值(重复的排列是相邻的)
void swap(char *p,char *q)
{
int temp;
temp=*p;
*p=*q;
*q=temp;
}
void perm(char str[],int k)//k表示前缀的位置,n代表数组长度
{

int i,n=strlen(str); //得到数组长度n
if(k==n-1) { //当前缀是最后一个位置时，输出数组
if(strcmp(index,str)!=0) puts(str); //与上一个排列结果进行比较，如果不相同，就输出。
strcpy(index,str); //保存当前排列
}
else{
for(i=k;i<n;i++) //否则执行循环
{
swap(&str[i],&str[k]); //交换前缀，使之产生下一个前缀
perm(str,k+1);
swap(&str[i],&str[k]); //将前缀换回来，继续做上一个前缀
}
}
}
void main()
{
int i,n;
char str[N];
index=malloc(N*sizeof(char)); //给index分配空间
printf("请输入一个字符串，将进行全排列。\n");
gets(str); //得到字符串
printf("全排列：\n");
perm(str,0,n); //以第一个元素为前缀进行全排列
}

Answer 1

请看下面的代码，在你的代码上做了稍许修改。修改的地方加上了注释 // Add。现在测试下来，可以实现不重复的全排序了。例如输入122，将得到
122
212
221
你可以再用1223, 1112233, 1122333等字符串来测试。
*********************************************************************

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include <algorithm>
#include <string>
#define N 100
void swap(char *p,char *q)
{
int temp;
temp=*p;
*p=*q;
*q=temp;
}
void perm( std::string str, int k ) // k表示前缀的位置
{
if( k == str.size() - 1 ) { //当前缀是最后一个位置时，输出数组
puts( str.c_str() );
}
else{
std::sort( str.begin() + k, str.end() ); // Add: 先排序，再执行循环
for( unsigned int i = k; i< str.size(); i++ )
{
if ( i != k && str[i-1] == str[i] ) // Add: 过滤掉重复的（因为已经排序了，重复的就是和前一个相等的）
continue;
swap(&str[i],&str[k]); //交换前缀，使之产生下一个前缀
perm(str,k+1);
swap(&str[i],&str[k]); //将前缀换回来，继续做上一个前缀
}
}
}
void main()
{
char str[N];
printf("请输入一个字符串，将进行全排列。\n");
gets(str); //得到字符串
printf("全排列：\n");
perm(str,0); //以第一个元素为前缀进行全排列
}