遍历组合的实现——VB2005

页面导航:首页 > 软件编程 > vb.net > 遍历组合的实现——VB2005

遍历组合的实现——VB2005

来源: 作者: 时间:2016-01-21 10:23 【

在数学的统计分支里,排列与组合是一个很重要的分支。在各种实际应用中,排列与组合也扮演了重要的角色。举例来说,安排人员参加活动可以看作是组合的应用。比方说,现在有十

       在数学的统计分支里,排列与组合是一个很重要的分支。在各种实际应用中,排列与组合也扮演了重要的角色。举例来说,安排人员参加活动可以看作是组合的应用。比方说,现在有十个人,选出其中的五个人参加某项集体活动。由于彼此之间有着脾气性格等因素,所以,不同的人员组合有着不同的工作效率。现在,要求你找出效率最高的人员安排。因为选出五人参加活动,没有顺序问题,因此是一个组合的问题。如果说,随机的选出一个组合,用计算机来实现是非常简单的,常见的"洗牌算法"就能实现。要找出效率最高的组合,只要遍历所有的组合即可。问题是如何遍历所有的组合。

      还是利用数学知识,我们知道组合函数C(m,n)代表着从n个人选m个人的组合的可能数。那么C(5,10)=252就表示本题有252种选择。如果,给每一种组合都标上标号,不同的标号代表不同的组合,这样遍历所有的组合就转化为遍历标号了。

 

      基于这个思想,完成下面的代码。其中,主函数有两个。

 

      一个是

         Public Shared Function C(ByVal C1 As Integer, ByVal C2 As Integer) As Integer

        用来计算组合数的,C1是上标,C2是下标。

           另一个是

Public Shared Function GetCombination( ByVal Lower As Integer, ByVal Upper As Integer, ByVal Count As Integer, ByVal Index As Integer) As Integer()

 

       这是根据参数返回一个组合,

      Lower表示返回组合的下限

      Upper表示返回组合的上限

      Count表示组合中的元素数

      Index表示该组合的标号

       要获得一个组合,直接调用即可。如:

      Dim T() as Integer

      T= GetCombination(1,10,5,20)

       这个表示返回本题的一个组合,其中20是标号

如果想随机得到一个组合,只要给一个随机的标号即可

要遍历组合,设置参数I即可。如:

Dim T() as Integer,I as Integer

For I=1 to C(5,10)

T=GetCombination(1,10,5,I)

DoSomeWork 执行根据组合计算效率的代码

Next

这样,就遍历了所有的组合

代码赋予其后,用的是VB2005

Public Class clsCombination

Public Shared Function GetCombination( ByVal Lower As Integer, ByVal Upper As Integer, ByVal Count As Integer, ByVal Index As Integer) As Integer()

If Count > Upper - Lower + 1 Then Return Nothing

If Count <= 0 Then Return Nothing

If Lower > Upper Then Return Nothing

If Lower < 0 OrElse Upper < 0 Then Return Nothing

 

Dim tS() As String = GetC(Lower, Upper, Count, Index).Split(",".ToCharArray, StringSplitOptions.RemoveEmptyEntries)

Dim tI() As Integer

ReDim tI(tS.GetUpperBound(0))

Dim i As Integer

 

For i = 0 To tI.GetUpperBound(0)

tI(i) = tS(i)

Next

Return tI

End Function

 

Private Shared Function GetC(ByVal Lower As Integer, ByVal Upper As Integer, ByVal Count As Integer, ByVal Index As Integer) As String

Dim i As Integer, tS As String

If Count = Upper - Lower + 1 Then

tS = ""

For i = Lower To Upper

tS &= i & ","

Next

Return tS

End If

Index = Index Mod C(Count, Upper - Lower + 1)

i = C(Count - 1, Upper - Lower)

 

If Index < i Then

tS = Lower & "," & GetC(Lower + 1, Upper, Count - 1, Index)

            Else

tS = GetC(Lower + 1, Upper, Count, Index - i)

End If

Return tS

End Function

Public Shared Function C(ByVal C1 As Integer, ByVal C2 As Integer) As Integer

If C1 < 0 OrElse C1 > C2 OrElse C2 <= 0 Then Return 0

If C1 = 0 Then Return 1

Dim i As Integer, S1 As Single = 1

For i = 1 To C1

S1 *= (C2 - i + 1) / i

Next

Return S1

End Function

End Class

作者:万仓一黍

Tags:

相关文章

    文章评论

    最 近 更 新
    热 点 排 行
    Js与CSS工具
    代码转换工具
    
    <