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