周遊組合的實作——VB2005

      在數學的統計分支裡，排列與組合是一個很重要的分支。在各種實際應用中，排列與組合也扮演了重要的角色。舉例來說，安排人員參加活動可以看作是組合的應用。比方說，現在有十個人，選出其中的五個人參加某項集體活動。由于彼此之間有着脾氣性格等因素，是以，不同的人員組合有着不同的工作效率。現在，要求你找出效率最高的人員安排。因為選出五人參加活動，沒有順序問題，是以是一個組合的問題。如果說，随機的選出一個組合，用計算機來實作是非常簡單的，常見的"洗牌算法"就能實作。要找出效率最高的組合，隻要周遊所有的組合即可。問題是如何周遊所有的組合。

      還是利用數學知識，我們知道組合函數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（代碼格式修正于2012年1月5日） 

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)

　　　　Return tS

　　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

　　　　Return S1

End Class