遍历排列的实现——VB2005
前两日，写了一篇“遍历组合的实现——VB2005”。在数学分支里，排列与组合是不分家的。于是，动手写下本文。在上一文中，采用了递归调用，虽然便于理解，但是算法的效率上打个折扣。本文一并重写，改为循环调用。
代码赋予其后，用的是VB2005
两个类，一个是clsPermutation，用来计算排列的；一个是clsCombination，用来计算组合的。下面，把各个函数说明一下。
类clsPermutation：
函数：GetPermutation
获得指定标号的排列，返回值是一个数组
参数： Lower，排列中的下限
Upper，排列中的上限
Count，排列中的元素的个数
Index，该排列的标号
示例： tI=GetPermutation（1，8，4，23）
返回一个从1到8中选4个数的一个排列，标号为23
函数：GetPermutationRandom
获得随机的排列，返回值是一个数组
参数： Lower，排列中的下限
Upper，排列中的上限
Count，排列中的元素的个数
示例： tI=GetPermutation（1，8，4）
返回一个从1到8中选4个数的一个排列
函数：Factorial
获得指定参数的阶乘，返回值是一个整数
参数： N，指定参数
示例： tI=Fratorial（4）
返回4的阶乘，为24
函数：P
获得指定参数的排列数，返回值是一个整数
参数： M，指定参数上标；N，指定参数下标
示例： tI=P（2，6）
计算P（2，6）的值，为30
类clsCombination：
函数：GetCombination
获得指定标号的排列，返回值是一个数组
参数： Lower，排列中的下限
Upper，排列中的上限
Count，排列中的元素的个数
Index，该排列的标号
示例： tI=GetCombination（1，8，4，23）
返回一个从1到8中选4个数的一个组合，标号为23
函数：GetCombinationRandom
获得随机的排列，返回值是一个数组
参数： Lower，排列中的下限
Upper，排列中的上限
Count，排列中的元素的个数
示例： tI=GetCombination（1，8，4）
返回一个从1到8中选4个数的一个组合
函数：C
获得指定参数的排列数，返回值是一个整数
参数： M，指定参数上标；N，指定参数下标
示例： tI=C（2，6）
计算C（2，6）的值，为15
代码格式修正于2012年1月5日
Public Class clsPermutation
Private Shared mList() As Integer
Public Shared Function GetPermutationRandom(ByVal Lower As Integer, ByVal Upper As Integer, ByVal Count 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 i As Integer
ReDim mList(Upper - Lower)
For i = 0 To mList.GetUpperBound(0)
mList(i) = Lower + i
Next
Dim tR As New Random
Call GetP(Upper - Lower + 1, Count, tR.Next(P(Count, Upper - Lower + 1)), 0)
ReDim Preserve mList(Count - 1)
Return mList
End Function
Public Shared Function GetPermutation(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
ReDim mList(Upper - Lower)
Dim i As Integer
For i = 0 To mList.GetUpperBound(0)
mList(i) = Lower + i
Next
Call GetP(Upper - Lower + 1, Count, Index, 0)
ReDim Preserve mList(Count - 1)
Return mList
End Function
Private Shared Sub GetP(ByVal Range As Integer, ByVal Count As Integer, ByVal Index As Integer, ByVal Start As Integer)
Dim i As Integer, j As Integer
Do While Count > 0
j = P(Count, Range)
Index = Index Mod j
i = Int(Index / (j / Range))
Call clsData.SwapNumber(mList(Start), mList(Start + i))
Range -= 1
Count -= 1
Start += 1
Loop
End Sub
Public Shared Function Factorial(ByVal N As Integer) As Integer
Dim i As Integer, S1 As Integer = 1
If N < 0 Then Return 0
For i = 1 To N
S1 *= i
Next
Return S1
End Function
Public Shared Function P(ByVal M As Integer, ByVal N As Integer) As Integer
Dim i As Integer, S1 As Integer = 1
For i = 1 To M
S1 *= (N - i + 1)
Next
Return S1
End Function
End Class
Public Class clsCombination
Private Shared mList() As Integer
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
ReDim mList(Count - 1)
Call GetC(Lower, Upper, Count, Index, 0)
Return mList
End Function
Public Shared Function GetCombinationRandom(ByVal Lower As Integer, ByVal Upper As Integer, ByVal Count 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
ReDim mList(Count - 1)
Dim tR As New Random
Call GetC(Lower, Upper, Count, tR.Next(C(Count, Upper - Lower + 1)), 0)
Return mList
End Function
Private Shared Sub GetC(ByVal Lower As Integer, ByVal Upper As Integer, ByVal Count As Integer, ByVal Index As Integer, ByVal Start As Integer)
Dim i As Integer
Do While Count < Upper - Lower + 1
Index = Index Mod C(Count, Upper - Lower + 1)
i = C(Count - 1, Upper - Lower)
If Index < i Then
mList(Start) = Lower
Lower += 1
Count -= 1
Start += 1
Else
Lower += 1
Index -= i
End If
Loop
For i = Lower To Upper
mList(i + Start - Lower) = i
Next
End Sub
Public Shared Function C(ByVal M As Integer, ByVal N As Integer) As Integer
If M < 0 OrElse M > N OrElse N <= 0 Then Return 0
If M = 0 Then Return 1
Dim i As Integer, S1 As Single = 1
For i = 1 To M
S1 *= (N - i + 1) / i
Next
Return S1
End Function
End Class