Description
设R={ r1, r2, ……,
rn }是要进行排列的n个元素。其中元素r1 ,r2 ,……,rn可能相同。试设计一个算法，列出R的所有不同排列。
给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。
Input
输入数据的的第1行是元素个数n，1≤n≤500。接下来的1行是待排列的n个元素。
Output
将计算出的n个元素的所有不同排列输出，每种排列占1行，最后1行中的数是排列总数。
Sample Input
4
aacc
Sample Output
aacc
acac
acca
caac
caca
ccaa
6
和普通求全排列问题差不多，只是多了，判断是否重复字符而已
#include
<iostream>
#include
<algorithm>
#include
<cstdio>
using namespace std ;
long long ans;
int ok(char str[],int a ,int b )
{
if(b>a)
for(int
i=a;i<b;i++)
if(str[i]==str[b])
return
0;
return
1;
}
void perm(char str[],int k,int m)
{
int
i;
if(k==m)
{
ans++;
for(i=0;i<=m;i++)
printf("%c",str[i]);
printf("\n");
return ;
}
else
for(i=k;i<=m;i++)
if(ok(str,k,i))
{
swap(str[k],str[i]);
perm(str,k+1,m);
swap(str[k],str[i]);
}
}
int main()
{
char
str[505];
int
n,i;
scanf("%d",&n);
getchar();
ans=0;
for(i=0;i<n;i++)
scanf("%c",&str[i]);
perm(str,0,n-1) ;
printf("%lld\n",ans);
return 0;
}
加载中，请稍候......
加载中…
喜欢