本文共 2411 字,大约阅读时间需要 8 分钟。
在数学的统计分支里,排列与组合是一个很重要的分支。在各种实际应用中,排列与组合也扮演了重要的角色。举例来说,安排人员参加活动可以看作是组合的应用。比方说,现在有十个人,选出其中的五个人参加某项集体活动。由于彼此之间有着脾气性格等因素,所以,不同的人员组合有着不同的工作效率。现在,要求你找出效率最高的人员安排。因为选出五人参加活动,没有顺序问题,因此是一个组合的问题。如果说,随机的选出一个组合,用计算机来实现是非常简单的,常见的“洗牌算法”就能实现。要找出效率最高的组合,只要遍历所有的组合即可。问题是如何遍历所有的组合。
还是利用数学知识,我们知道组合函数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
转载地址:https://blog.csdn.net/grenet/article/details/4615779 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!