vb 排列组合算法
2010-05-10 18:42:37| 分类：
编程相关
| 标签：
|举报
|字号大中小 订阅
这是一个类模块的代码
Option Explicit
' 所谓回溯：就是搜索一棵状态树的过程，这个过程类似于图的深度优先
' 搜索（DFS），在搜索的每一步（这里的每一步对应搜索树的第i层）中
'产生一个正确的解，然后在以后的每一步搜索过程中，都检查其前一步
'的记录，并且它将有条件的选择以后的每一个搜索状态（即第i+1层的 状态节点）。
' 需掌握的基本算法：
'排列：就是从n个元素中同时取r个元素的排列，记做P(n,m)。(当m=n时，
'我们称P(n,n)=n!为全排列) 例如我们有集合OR = {1,2,3,4},那么
' n = |OR| = 4, 且规定r=3, 那么P(4,3)就是:
'{1,2,3}; {1,2,4}; {1,3,2}; {1,3,4}; {1,4,2}; {1,4,3};
' {2,1,3}; {2,1,4}; {2,3,1}; {2,3,4}; {2,4,1}; {2,4,3};
' {3,1,2}; {3,1,4}; {3,2,1}; {3,2,4}; {3,4,1}; {3,4,2};
'{4,1,2}; {4,1,3}; {4,2,1}; {4,2,3}; {4,3,1}; {4,3,2}
Private n As Integer, m As Integer
Private pNum As Integer
Private used() As Integer
Private p() As String
Private Data As Variant
Private PData As Variant
'排列组合
Public Sub Permute(vData As Variant, iPm As Integer, vPData As Variant)
Data = vData
n = UBound(vData) - LBound(vData) + 1
If iPm <= n Then
m = iPm
Else
m = n
End If
ReDim used(n - 1)
ReDim p(m - 1)
pNum = 0
ReDim PData(Pnm(n, m) - 1, m - 1)
Permute0 0
vPData = PData
End Sub
'组合
Public Sub Combine(vData As Variant, iPm As Integer, vPData As Variant)
Data = vData
n = UBound(vData) - LBound(vData) + 1
If iPm <= n Then
m = iPm
Else
m = n
End If
ReDim used(n - 1)
ReDim p(m - 1)
pNum = 0
ReDim PData(Cnm(n, m) - 1, m - 1)
Combine0 0, 0
vPData = PData
End Sub
' permute(pos -- 表示在解空间中填写数据的下标位置)
'{ 如果解空间填写满了 打印解空间当前的排列结果 函数返回
' for (i=0; i<n; i++) -- n是待排列数据总数
' {
' 尝试在这个下标位置填写每一个待排列的数据
' (但这些数据可填写的前提是数据没有被标记为已使用)
'
' 填写后, 把这个下标为i的数据标记为已使用 '
' permute(pos+1); -- 填写解空间中下一个位置 '
' 下标为i的数据已参与了解空间下标pos处的排列 '
'取消已使用标记(因为该数据可以在解空间其他下标处使用)
' 继续for循环考察下一个待排列数据
' }
' }
'
' used[i] == 1 - 待排列空间中下标i处的数据已被使用;
' used[i] == 0 - 可以使用待排列空间中下标i处的数据;
Private Sub Permute0(pos As Integer)
Dim i As Integer
If pos = m Then
For i = 0 To m - 1
PData(pNum, i) = p(i)
Next
pNum = pNum + 1
Exit Sub
End If
For i = 0 To n - 1
If used(i) = 0 Then
used(i) = used(i) + 1
p(pos) = Data(i)
Permute0 (pos + 1)
used(i) = used(i) - 1
End If
Next i
End Sub
'组合
'idx--记录下标pos处的i的位置
Private Sub Combine0(pos As Integer, idx As Integer)
Dim i As Integer
If pos = m Then
For i = 0 To m - 1
PData(pNum, i) = p(i)
Next
pNum = pNum + 1
Exit Sub
End If
For i = idx To n - 1
If used(i) = 0 Then
used(i) = used(i) + 1
p(pos) = Data(i)
Combine0 (pos + 1), i
used(i) = used(i) - 1
End If
Next i
End Sub
'计算排列组合的个数
'n*(n-1)*(n-2)*...*(n-m+1) m个
Public Function Pnm(n As Integer, m As Integer) As Long
If m > n Then
m = n
End If
If m = 0 Then
Pnm = 1
Exit Function
Else
Pnm = n * Pnm(n - 1, m - 1)
End If
End Function
'计算组合的个数
Public Function Cnm(n As Integer, m As Integer) As Long
If m > n Then
m = n
End If
Cnm = Pnm(n, m) / Pnm(m, m)
End Function
****************************************************
Dim a As New Class1
Dim v1(2) As Integer
Dim v2
v1(0) = 1: v1(1) = 2: v1(2) = 3
a.Permute v1, 3, v2
v2为二维数组,V2(5,2)
评论这张
转发至微博
转发至微博
评论