posts - 225, comments - 62, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

排列组合的类实现

Posted on 2006-04-12 17:31 魔のkyo 阅读(203) 评论(0)  编辑 收藏 引用 所属分类: Programming
#include  < iostream >
#include  < stdlib.h >
using   namespace  std;

typedef  char  TdfsType; // 所排列元素类型定义
/*
class Tdfs是一个进行排列的类
构造函数Tdfs(int nn,int kk,TdfsType *ddata);
对ddata数组中的前nn项做nn P kk的排列,即nn取kk任取,对每种排列执行function函数
 */
class  Tdfs{
 private :
    TdfsType  *  a, * data;
     int   *  used, k,n; // n P k
     void  dfs( int  d);
     void  function( void );
 public :
    Tdfs( int  nn, int  kk,TdfsType  * ddata);
     ~ Tdfs(){delete [] a;delete [] used;};
    
};
Tdfs::Tdfs( int  nn, int  kk,TdfsType  * ddata){
    n = nn;k = kk;data = ddata;
    a = new  TdfsType [n];
    used = new   int  [n];
     for ( int  i = 0 ;i < n;i ++ )a[i] = used[i] = 0 ;
    dfs( 0 );
}
 void   Tdfs::dfs ( int  d){
     if  (d == k){ // 找到一种排列
        function();
    }
     else {
         for ( int  i = 0 ;i < n;i ++ ){
             if  (used[i] == 0 ){
                used[i]  =   1 ;
                a[d]  =  data[i];
                dfs (d + 1 );
                used[i]  =   0 ;
            } // if
        } // for
    }
}
 void  Tdfs::function( void ){
     /* 修改此函数可以对得到的每种排列进行操作,例如输出
    a[i]是传入数据的副本可以进行修改
    for(int i=0;i<k;i++)cout<<a[i];
    cout<<endl;
     */
     for ( int  i = 0 ;i < k;i ++ )cout << a[i];
    cout << endl;
}


 int  main(){
    TdfsType array[ 4 ] = { ' a ' , ' b ' , ' c ' , ' d ' };
    Tdfs a( 4 , 3 ,array);
  //    system("pause");
     return   0 ;
}
只有注册用户登录后才能发表评论。