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


 

上一篇:正则表达式——去除文本中的非汉字(VB2005)


下一篇:计算机中的颜色VIII——快速计算颜色的偏转