1908 - 有重复元素的排列问题
设<span>R={r<sub>1</sub>, r<sub>2 </sub>,…, r<sub>n</sub>}</span>是要进行排列的<span>n </span>个元素。其中元素 <span>r<sub>1</sub>,
r2 ,…, rn可能相同。试设计
一个算法，列出<span>R </span>的所有不同排列。<span> </span>
<br />
<span></span><span> </span>
<span> </span>
编程任务：<span> </span>
给定<span>n </span>以及待排列的<span>n </span>个元素。计算出这<span>n </span>个元素的所有不同排列。<span> </span>
Input
输入的第1 行是元素个数n，1<=n<=500。接下来的1 行
是待排列的n 个元素。
Output
程序运行结束时，将计算出的n 个元素的所有不同排列输出。
最后1 行中的数是排列总数。
Examples
Input
4 aacc
Output
aacc acac acca caac caca ccaa 6
Solution C
#include <stdio.h> #define max 500 int count=0; int repeat(char str[],int a ,int b ) { int i; if(b>a) for(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) { count++; for(i=0;i<=m;i++) printf("%c",str[i]); printf("\n"); return ; } else for(i=k;i<=m;i++) if(repeat(str,k,i)) { char t; t=str[i]; str[i]=str[k]; str[k]=t; perm(str,k+1,m); t=str[i]; str[i]=str[k]; str[k]=t; } } int main() { char str[max]; int n,i; scanf("%d",&n); getchar(); for(i=0;i<n;i++) scanf("%c",&str[i]); perm(str,0,n-1) ; printf("%d\n",count); return 0; }
Solution C++
#include <iostream> #include <algorithm> using namespace std ; 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++ ) { cout<<str[i]; } cout<<endl; } 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(int argc, char* argv[]) { char str[1000]; int n , i ; cin>>n ; ans = 0 ; for( i = 0 ; i < n ; i ++) cin>>str[i]; perm(str,0,n-1) ; cout<<ans<<endl; return 0; }