加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

vb排列组合算法

(2010-07-08 20:56:20)
标签:

vb

排列组合

算法

源码

it

分类: 开发

这是一个类模块的代码  
Option   Explicit   
  所谓回溯:就是搜索一棵状态树的过程,这个过程类似于图的深度优先  
  搜索(DFS),在搜索的每一步(这里的每一步对应搜索树的第i层)中  
'产生一个正确的解,然后在以后的每一步搜索过程中,都检查其前一步  
'的记录,并且它将有条件的选择以后的每一个搜索状态(即第i+1层的     状态节点)。   
  需掌握的基本算法:  
'排列:就是从n个元素中同时取r个元素的排列,记做P(n,m)。(当m=n时,  
'我们称P(n,n)=n!为全排列)   例如我们有集合OR    {1,2,3,4},那么  
    |OR|    4,   且规定r=3,   那么P(4,3)就是:  
'{1,2,3};   {1,2,4};   {1,3,2};   {1,3,4};   {1,4,2};   {1,4,3};  
  {2,1,3};   {2,1,4};   {2,3,1};   {2,3,4};   {2,4,1};   {2,4,3};  
  {3,1,2};   {3,1,4};   {3,2,1};   {3,2,4};   {3,4,1};   {3,4,2};  
'{4,1,2};   {4,1,3};   {4,2,1};   {4,2,3};   {4,3,1};   {4,3,2}     
Private    As   Integer,    As   Integer  
Private   pNum   As   Integer  
Private   used()   As   Integer  
Private   p()   As   String  
Private   Data   As   Variant  
Private   PData   As   Variant    
'排列组合  
Public   Sub   Permute(vData   As   Variant,   iPm   As   Integer,   vPData   As   Variant)           
          Data    vData  
            UBound(vData)    LBound(vData)    
          If   iPm   <=    Then  
                    iPm  
          Else  
                    
          End   If  
           
          ReDim   used(n    1)  
          ReDim   p(m    1)  
           
          pNum    
          ReDim   PData(Pnm(n,   m)    1,     1)  
           
          Permute0   
           
          vPData    PData  
           
End   Sub  
   
'组合  
Public   Sub   Combine(vData   As   Variant,   iPm   As   Integer,   vPData   As   Variant)  
           
          Data    vData  
            UBound(vData)    LBound(vData)    
           
          If   iPm   <=    Then  
                    iPm  
          Else  
                    
          End   If  
           
          ReDim   used(n    1)  
          ReDim   p(m    1)  
           
          pNum    
          ReDim   PData(Cnm(n,   m)    1,     1)  
          Combine0   0,   
          vPData    PData  
           
End   Sub  
   
   
  permute(pos   --   表示在解空间中填写数据的下标位置)  
'{               如果解空间填写满了   打印解空间当前的排列结果   函数返回  
      for   (i=0;   i<n;   i++)   --   n是待排列数据总数  
      
              尝试在这个下标位置填写每一个待排列的数据  
              (但这些数据可填写的前提是数据没有被标记为已使用)  
 
      填写后,   把这个下标为i的数据标记为已使用   
      permute(pos+1);   --   填写解空间中下一个位置   
      下标为i的数据已参与了解空间下标pos处的排列   
'取消已使用标记(因为该数据可以在解空间其他下标处使用)  
      继续for循环考察下一个待排列数据  
      
  
 
  used[i]   ==     待排列空间中下标i处的数据已被使用;  
  used[i]   ==     可以使用待排列空间中下标i处的数据;  
   
Private   Sub   Permute0(pos   As   Integer)  
Dim    As   Integer  
          If   pos     Then  
                  For      To     
                          PData(pNum,   i)    p(i)  
                  Next  
                  pNum    pNum    
                  Exit   Sub  
          End   If  
          For      To     
                  If   used(i)     Then  
                          used(i)    used(i)    
                          p(pos)    Data(i)  
                          Permute0   (pos    1)  
                          used(i)    used(i)    
                  End   If  
          Next   
                   
End   Sub  
   
'组合  
'idx--记录下标pos处的i的位置  
Private   Sub   Combine0(pos   As   Integer,   idx   As   Integer)  
Dim    As   Integer  
          If   pos     Then  
                  For      To     
                          PData(pNum,   i)    p(i)  
                  Next  
                  pNum    pNum    
                  Exit   Sub  
          End   If  
          For     idx   To     
                  If   used(i)     Then  
                          used(i)    used(i)    
                          p(pos)    Data(i)  
                          Combine0   (pos    1),   
                          used(i)    used(i)    
                  End   If  
          Next   
   
End   Sub  
   
'计算排列组合的个数  
'n*(n-1)*(n-2)*...*(n-m+1)   m个  
Public   Function   Pnm(n   As   Integer,    As   Integer)   As   Long  
          If      Then  
                    
          End   If  
          If      Then  
                  Pnm    
                  Exit   Function  
          Else  
                  Pnm      Pnm(n    1,     1)  
          End   If  
           
End   Function  
   
'计算组合的个数  
Public   Function   Cnm(n   As   Integer,    As   Integer)   As   Long  
          If      Then  
                    
          End   If  
          Cnm    Pnm(n,   m)    Pnm(m,   m)  
           
End   Function  
****************************************************
Dim    As   New   Class1  
Dim   v1(2)   As   Integer  
Dim   v2  
          v1(0)    1:   v1(1)    2:   v1(2)    
          a.Permute   v1,   3,   v2  
   
v2为二维数组,V2(5,2)

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有