全排列的随机散列的实现（VB2005）
发布时间：2020-12-16 23:25:10 所属栏目：大数据 来源：网络整理
导读：在实际的编程中，有时会需要遍历一组数字的全排列，来获得计算的结果。这在解某些最优解的题目的时候，特别有用。 例如：现在有4个人去完成4项任务，每人只能完成一项任务，每人完成各个任务的效率都不同。那如何安排才能使得总效率最高？这是一个任务指派的
|
在实际的编程中，有时会需要遍历一组数字的全排列，来获得计算的结果。这在解某些最优解的题目的时候，特别有用。
例如：现在有4个人去完成4项任务，每人只能完成一项任务，每人完成各个任务的效率都不同。那如何安排才能使得总效率最高？这是一个任务指派的问题，我们可以使用匈牙利法解决，这不是本篇文章的讨论重点，有兴趣的读者可以参看有关文章。如果，我们遍历1-4的全排列，分别求出每种全排列的效率和，然后取最大的一组解。这也是解题的一种思路。
在上一篇文章中，我们可以给定上下限得到一个随机散列。但是如何遍历呢？有人会说，我不停得到随机散列，和已得到的随机散列比较，相同的就再重新得到一个随机散列。这样，迟早会遍历所有的全排列。这有一个问题，到后期的时候，重复的可能性相当高，会极度影响程序运行的效率。
换一个思路，以上题为例，学过排列组合的都知道，全排列的可能性一共有4！=4×3×2×1=24种可能。我能不能给定一个参数就能获得一个全排列呢？比方说，给定13得到一个全排列，给定7得到另一个全排列。这样，只要遍历参数从1到24就能得到所有的全排列。
下面给出这个思路的程序代码，用的是VB2005
'函数名：GetRandomList
'作用：获得一个全排列的散列
'参数Value：指定全排列的参数标号
'参数Count：全排列中数字的个数
Public Function GetRandomList( _
ByVal Value As Integer,_
ByVal Count As Integer _
) As Integer()
Dim mBase() As Integer,mN As Integer
Dim i As Integer,j As Integer
If Count <= 0 Then Return Nothing
mN = N(Count)
If Value > mN - 1 OrElse Value < 0 Then Value = Value Mod mN
ReDim mBase(Count - 1)
For i = 0 To Count - 1
mBase(i) = i + 1
Next
For i = Count To 2 Step -1
mN = mN / i
j = Int(Value / mN)
Call SwapNumber(mBase(j),mBase(i - 1))
Value = Value Mod mN
Next
Return mBase
End Function
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |