有重复元素的排列问题

Time Limit:10000MS  MemoryLimit:65536K
Total Submit:181 Accepted:87

Description

设R={ r , r , , rn 1 2 ?}是要进行排列的n个元素。其中元素n r , r , , r 1 2 ? 可能相同。试设计
一个算法，列出R的所有不同排列。

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

Input

输入数据的第1行是元素个数n，1￡n￡500。接下来的1 行是待排列的n个元素。

Output

程序运行结束时，将计算出的n个元素的所有不同排列输出，最后1 行中的数是排列总数。

SampleInput

 

4aacc

 

SampleOutput

 

aaccacacaccacaaccacaccaa6

//code c++ vc6.0

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