遍历排列的实现——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

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 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 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) For i = 0 To mList.GetUpperBound(0) mList(i) = Lower + i Next Call GetP(Upper - Lower + 1,Index,0) ReDim Preserve mList(Count - 1) Return mList End Function Private Shared Sub GetP(ByVal Range 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 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,0) Return mList End Function Public Shared Function GetCombinationRandom(ByVal Lower 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,tR.Next(C(Count,0) Return mList End Function Private Shared Sub GetC(ByVal Lower 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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!