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


 

时间: 2024-10-26 08:01:30

遍历排列的实现——VB2005的相关文章

遍历组合的实现——VB2005

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

再议“生成全排列算法”

看了"白话算法(7) 生成全排列的几种思路(一)"和"白话算法(7) 生成全排列的几种思路(二) 康托展开".在此,将以前本人推导的全排列算法介绍一下,和广大的网友交流一下. 以例子说明,用0.1.2.3,四个数组成全排列. 首先可以知道,这四个数组成的全排列一共有4!=24个.那么给这24个全排列编号,分别为0.1.2--23.再给定一个算法,通过编号计算出一个全排列.本文的目的就是找到这样的算法. 把所有的全排列列举出来可以发现,0在末位的有6个,1在末位的有6

回溯法 -数据结构与算法

1.回溯法算法思想:   定义:         回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 1.回溯法适用:有许多问题,当需要找出它的解集(全部解)或者要求回答什么解是满足某些约束条件的最优解时,往往要使用回溯法. 2.有组织的穷举式搜索:回溯法的基本做法是搜索或者有的组织穷尽搜索.它能避免搜索所有的可能

python 回溯法 记录

一直不是太理解回溯法,这几天集中学习了一下,记录如下. 回溯法有"通用的解题法"之称. 1.定义:  也叫试探法,它是一种系统地搜索问题的解的方法. 2.基本思想:  从一条路往前走,能进则进,不能进则退回来,换一条路再试. 3.一般步骤:   定义一个解空间(子集树.排列树二选一) 利用适于搜索的方法组织解空间.   利用深度优先法搜索解空间.   利用剪枝函数避免移动到不可能产生解的子空间. 4.约束函数: 是否满足显约束(存在) 5.限界函数: 是否满足隐约束(最优) 6.子集树

数学问题,遍历所有排列

问题描述 N个互不相同的数,放在一个数组里每次交换两个,在遍历玩所有排列前不出现重复.how 解决方案 解决方案二:遍历数组中元素的所有组合--全排列publicclassAllSort{int[]result;publicAllSort(int[]i){result=newint[i.length];}publicstaticvoidmain(String[]args){int[]i={1,2,3,4,5};AllSorttest=newAllSort(i);test.method(i,0,i

组合排列遍历算法浅析(一)

最近一段时间,稍微空闲了些,于是准备把去年面试某公司时遇到的题写出来. 回味那次面试,真是有点尴尬,大学毕业后,一直忙于这样技术.那样技术,此控件.彼控件的,对于基础的东西忘得差不多了. 于是乎,在面试官一道问题下,顿显尴尬.不过这个面试官的面试方法我觉得挺变态的-- 通过了第一轮电面,第二轮笔试,开始了第三轮面试的时候,面试官开始问一些工作经历上的事情.问得差不多的时候,突然来一句, 这里有一道比较简单的算法题,你来解一下喃: 有n个数,打印出取其中m个数的所有组合. 我当时脑中只记得了C(n

php 遍历数据表数据并列表横向排列的代码_php技巧

复制代码 代码如下: <?php $a = array (1,2,3,4,5,6,7,8,9,10,11); $i = 0; ?> <table border=1> <tr> <? foreach ($a as $k){ if($i%3==0) {//该处表示需要横向排列的列数. echo "</tr><tr>"; } echo "<td>",$k,"</td>&qu

树与森林的存储、遍历和树与森林的转换

树的存储结构     双亲表示法   孩子表示法: (a)多重链表(链表中每个指针指向一棵子树的根结点); (b)把每个跟结点的孩子结点排列起来,看成一个线性表,且以单链表做存储结构.且N个头指针也组成一个线性表.   孩子兄弟表示法://二叉树表示法或二叉链表表示法 以二叉链表做树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点(fchild 和nsibling) //孩子兄弟表示法 typedef struct CSNode{ int data; CSNode

二叉树的层序遍历概述

前面有篇博客详细分析了二叉树三种遍历(前序.中序.后序)方式的递归与非递归实现,参见:http://blog.csdn.net/ns_code/article/details/12977901,但把二叉树的层序遍历算法给漏掉了,实际上也不能说漏掉了,毕竟层序遍历的实现方法与这三种遍历的实现方法有所不同,因此单独拿出来分析比较合适. 二叉树的层序遍历的实现还是比较简单的,由于其层级的关系,很明显要用到队列来辅助实现,主要是从左向右,自上而下,依次将二叉树的各节点入队,这样便可以保证输出的顺序是层序