华师一附中OI组

标题: P1691 有重复元素的排列问题 [打印本页]

作者: admin 时间: 2018-5-10 12:08
标题: P1691 有重复元素的排列问题
题目描述
设R={r1，r2，……，rn}是要进行排列的n个元素。其中元素r1，r2，……，rn可能相同。使设计一个算法，列出R的所有不同排列。

给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。

输入输出格式
输入格式：
第1行：元素个数n（1<=n<500）

第2行：一行字符串，待排列的n个元素

输出格式：
计算出的n个元素的所有不同排列，最后一行是排列总数。

输入输出样例
输入样例#1：
4
aacc
输出样例#1：
aacc
acac
acca
caac
caca
ccaa
6
说明
输出按字典顺序排

作者: wzd(temp) 时间: 2018-5-12 13:58

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int M=512;
int n;
int tot;
typedef struct node
{
char c;
int cnt;
}CHAR;
CHAR a[M];
int t=0;
bool cmp(const CHAR a,const CHAR b)
{
return a.c<b.c;
}
void init()
{
char str[M];
bool X[M];
memset(X,true,sizeof(X));
scanf("%d",&n);
scanf("%s",str);
for(int i=0;i<n;i++)
{
if(X[i])
{
a[t].c=str[i];
for(int j=i;j<n;j++)
{
if(X[j] && str[i]==str[j])
{
X[j]=false;
a[t].cnt++;
}
}
t++;
}
}
sort(a,a+t,cmp);
return ;
}
char ORZ[M];
long long ans=0;
void dfs(int i)
{
if(i==n)
{
ans++;
for(int qwe=0;qwe<n;qwe++)
printf("%c",ORZ[qwe]);
printf("\n");
return ;
}
for(int ii=0;ii<t;ii++)
{
if(a[ii].cnt>0)
{
ORZ[i]=a[ii].c;
a[ii].cnt--;
dfs(i+1);
a[ii].cnt++;
}
}
return ;
}
int main()
{
init();
dfs(0);
printf("%lld\n",ans);
return 0;
}

复制代码

//orz

作者: 黄煦喆 时间: 2018-5-13 20:57

#include<iostream>
#include<map>
using namespace std;
int n,ans,a[30];
char ch,t[600];
map<char,short>cs;
map<short,char>sc;
void ms(int i)
{
if(i>n)
{
for(int i=1;i<=n;i++)cout<<t[i];
cout<<endl;
ans++;
}
else for(int k=1;k<=26;k++)
{
if(a[k])
{
t[i]=sc[k];
a[k]--;
ms(i+1);
a[k]++;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=26;i++)
{
cs.insert(make_pair(char(i+'a'-1),i));
sc.insert(make_pair(i,char(i+'a'-1)));
}
for(int i=1;i<=n;i++)
{
cin>>ch;
a[cs[ch]]++;
}
ms(1);
cout<<ans;
return 0;
}

复制代码

diggersun：好像没有说只有26个字母吧，要是有大小写呢？

作者: 吴语林 时间: 2018-5-14 06:47

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
int n,book[600],all=0;
char a[600],cun[600];
void dfs(int cen)
{
if(cen==n)
{
puts(cun),all++;
return;
}
int boln[26]={0};
for(int i=0;i<n;i++)
if(!book[i]&&!boln[a[i]-'a'])
{
book[i]=1,boln[a[i]-'a']=1,cun[cen]=a[i];
dfs(cen+1);
book[i]=0;
}
}
int main()
{
scanf("%d%s",&n,a);
sort(a,a+n);
dfs(0);
printf("%d",all);
return 0;
}

复制代码

作者: 张笑宇 时间: 2018-5-17 21:58

#include<iostream>
using namespace std;
int l,i,c[110],a[510],ans=0;///a记录
string s;
char aa[100];
void dfs(int x)
{
int j;
if (x==l+1)
{
ans++;
for (i=1; i<=l; i++) cout<<aa[a[i]];
cout<<endl;
}
else
{
for (j=1; j<=26; j++)
{
if (c[j]>0)
{
c[j]--;
a[x]=j;
dfs(x+1);
c[j]++;
}
}
}
}
int main()
{
cin>>l>>s;
for (i=0; i<=l-1; i++)
{
c[s[i]-96]++;
aa[s[i]-96]=s[i];
}
dfs(1);
cout<<ans;
return 0;
}

复制代码

作者: 黄煦喆 时间: 2018-5-19 20:52
本帖最后由黄煦喆于 2018-5-19 20:54 编辑

#include<iostream>
using namespace std;
int n,a[200],ans;
string s;
char k[600];
void ms(int i)
{
if(i>n)
{
for(int p=1;p<=n;p++)cout<<k[p];
cout<<endl;
ans++;
}
else for(int j=32; j<=126; j++)
if(a[j]>0)
{
a[j]--;
k[i]=char(j);
ms(i+1);
a[j]++;
}
}
int main()
{
cin>>n;
cin>>s;
for(int i=0; i<n; i++)a[int(s[i])]++;
ms(1);
cout<<ans;
return 0;
}

复制代码

作者: liubo 时间: 2018-5-20 15:39
使用STL中“下一个排列”即可得出结果

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[505];
int n,cou;
int main(){
scanf("%d%s",&n,s);
sort(s,s+n);
do{
printf("%s\n",s);
cou++;
}while(next_permutation(s,s+n));
printf("%d",cou);
return 0;
}

复制代码

作者: t20020125 时间: 2018-7-4 20:53
///lg1691
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int b[26];
char ss[1000];
int counts=0;
void dfs(int x)
{
if(x>=n)
{
      for(int i=0;i<=n-1;i++)
      {
         cout<<ss[i];
      }
      cout<<endl;
         counts++;
}
else
{
      for(int i=0;i<=25;i++)
         if(b[i]!=0)
      {
         b[i]--;
         ss[x]=i+'a';
         dfs(x+1);
         b[i]++;
      }
}
}
string s;
int main()
{
cin>>n;
cin>>s;
for(int i=0;i<s.size();i++)
{
      b[s[i]-'a']++;
}
dfs(0);
cout<<counts;
return 0;
}

欢迎光临华师一附中OI组 (http://hsyit.cn/)