P1691 有重复元素的排列问题

admin

题目描述
设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)

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. #include <cstring>
   
4. #include <algorithm>
   
5. using namespace std;
   
6. const int M=512;
   
7. int n;
   
8. int tot;
   
9. typedef struct node
   
10. {
    
11.         char c;
    
12.         int cnt;
    
13. }CHAR;
    
14. CHAR a[M];
    
15. int t=0;
    
16. bool cmp(const CHAR a,const CHAR b)
    
17. {
    
18.         return a.c<b.c;
    
19. }
    
20. void init()
    
21. {
    
22.         char str[M];
    
23.         bool X[M];
    
24.         memset(X,true,sizeof(X));
    
25.        
    
26.         scanf("%d",&n);
    
27.         scanf("%s",str);
    
28.        
    
29.         for(int i=0;i<n;i++)
    
30.         {
    
31.                 if(X[i])
    
32.                 {
    
33.                         a[t].c=str[i];
    
34.                         for(int j=i;j<n;j++)
    
35.                         {
    
36.                                 if(X[j] && str[i]==str[j])
    
37.                                 {
    
38.                                         X[j]=false;
    
39.                                         a[t].cnt++;
    
40.                                 }
    
41.                         }
    
42.                         t++;
    
43.                 }
    
44.         }
    
45.        
    
46.         sort(a,a+t,cmp);
    
47.        
    
48.         return ;
    
49. }
    
50. 
    
51. char ORZ[M];
    
52. long long ans=0;
    
53. void dfs(int i)
    
54. {
    
55.         if(i==n)
    
56.         {
    
57.                 ans++;
    
58.                 for(int qwe=0;qwe<n;qwe++)
    
59.                         printf("%c",ORZ[qwe]);
    
60.                 printf("\n");
    
61.                 return ;
    
62.         }
    
63.         for(int ii=0;ii<t;ii++)
    
64.         {
    
65.                 if(a[ii].cnt>0)
    
66.                 {
    
67.                         ORZ[i]=a[ii].c;
    
68.                         a[ii].cnt--;
    
69.                         dfs(i+1);
    
70.                         a[ii].cnt++;
    
71.                 }
    
72.         }
    
73.        
    
74.         return ;
    
75. }
    
76. 
    
77. int main()
    
78. {
    
79.         init();
    
80.        
    
81.         dfs(0);
    
82.         printf("%lld\n",ans);
    
83.        
    
84.         return 0;
    
85. }

复制代码

//orz

黄煦喆

1. #include<iostream>
   
2. #include<map>
   
3. using namespace std;
   
4. int n,ans,a[30];
   
5. char ch,t[600];
   
6. map<char,short>cs;
   
7. map<short,char>sc;
   
8. void ms(int i)
   
9. {
   
10.     if(i>n)
    
11.     {
    
12.         for(int i=1;i<=n;i++)cout<<t[i];
    
13.         cout<<endl;
    
14.         ans++;
    
15.     }
    
16.     else for(int k=1;k<=26;k++)
    
17.     {
    
18.         if(a[k])
    
19.         {
    
20.             t[i]=sc[k];
    
21.             a[k]--;
    
22.             ms(i+1);
    
23.             a[k]++;
    
24.         }
    
25.     }
    
26. }
    
27. int main()
    
28. {
    
29.     cin>>n;
    
30.     for(int i=1;i<=26;i++)
    
31.     {
    
32.         cs.insert(make_pair(char(i+'a'-1),i));
    
33.         sc.insert(make_pair(i,char(i+'a'-1)));
    
34.     }
    
35.     for(int i=1;i<=n;i++)
    
36.     {
    
37.         cin>>ch;
    
38.         a[cs[ch]]++;
    
39.     }
    
40.     ms(1);
    
41.     cout<<ans;
    
42.     return 0;
    
43. }
    

复制代码

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

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cstring>
   
4. #include <cstdio>
   
5. #include <cstdlib>
   
6. using namespace std;
   
7. int n,book[600],all=0;
   
8. char a[600],cun[600];
   
9. void dfs(int cen)
   
10. {
    
11.         if(cen==n)
    
12.         {
    
13.                 puts(cun),all++;
    
14.                 return;
    
15.         }
    
16.         int boln[26]={0};
    
17.         for(int i=0;i<n;i++)
    
18.                 if(!book[i]&&!boln[a[i]-'a'])
    
19.                 {
    
20.                         book[i]=1,boln[a[i]-'a']=1,cun[cen]=a[i];
    
21.                         dfs(cen+1);
    
22.                         book[i]=0;
    
23.                 }
    
24. }
    
25. int main()
    
26. {
    
27.         scanf("%d%s",&n,a);
    
28.         sort(a,a+n);
    
29.         dfs(0);
    
30.         printf("%d",all);
    
31.         return 0;
    
32. }

复制代码

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. int l,i,c[110],a[510],ans=0;///a记录
   
4. string s;
   
5. char aa[100];
   
6. void dfs(int x)
   
7. {
   
8.     int j;
   
9.     if (x==l+1)
   
10.     {
    
11.         ans++;
    
12.         for (i=1; i<=l; i++) cout<<aa[a[i]];
    
13.         cout<<endl;
    
14.     }
    
15.     else
    
16.     {
    
17.         for (j=1; j<=26; j++)
    
18.         {
    
19.             if (c[j]>0)
    
20.             {
    
21.                 c[j]--;
    
22.                 a[x]=j;
    
23.                 dfs(x+1);
    
24.                 c[j]++;
    
25.             }
    
26.         }
    
27.     }
    
28. }
    
29. int main()
    
30. {
    
31.     cin>>l>>s;
    
32.     for (i=0; i<=l-1; i++)
    
33.     {
    
34.         c[s[i]-96]++;
    
35.         aa[s[i]-96]=s[i];
    
36.     }
    
37.     dfs(1);
    
38.     cout<<ans;
    
39.     return 0;
    
40. }

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a[200],ans;
   
4. string s;
   
5. char k[600];
   
6. void ms(int i)
   
7. {
   
8.     if(i>n)
   
9.     {
   
10.         for(int p=1;p<=n;p++)cout<<k[p];
    
11.         cout<<endl;
    
12.         ans++;
    
13.     }
    
14.     else for(int j=32; j<=126; j++)
    
15.             if(a[j]>0)
    
16.             {
    
17.                 a[j]--;
    
18.                 k[i]=char(j);
    
19.                 ms(i+1);
    
20.                 a[j]++;
    
21.             }
    
22. }
    
23. int main()
    
24. {
    
25.     cin>>n;
    
26.     cin>>s;
    
27.     for(int i=0; i<n; i++)a[int(s[i])]++;
    
28.     ms(1);
    
29.     cout<<ans;
    
30.     return 0;
    
31. }
    

复制代码

liubo

使用STL中“下一个排列”即可得出结果

1. #include<cstdio>
   
2. #include<cstring>
   
3. #include<algorithm>
   
4. using namespace std;
   
5. char s[505];
   
6. int n,cou;
   
7. int main(){
   
8.     scanf("%d%s",&n,s);
   
9.     sort(s,s+n);
   
10.     do{
    
11.         printf("%s\n",s);
    
12.         cou++;
    
13.     }while(next_permutation(s,s+n));
    
14.     printf("%d",cou);
    
15.     return 0;
    
16. }

复制代码

t20020125

///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;
}