【新手进阶】之二十三：从二进制到组合算法

roych

去年圣诞节的时候，有版友提出如何处理组合问题（http://www.office-cn.net/thread-126791-1-1.html）。后面看了下，貌似迄今还没解决。于是就冒昧写一下。其实算组合并不难。无非是选择或不选某个元素，然后根据已选的元素个数进行判断罢了。
这么一来，我们就可以用二进制的思路来处理了。数组则转为2的n次方（n为元素个数）。比如，我们可以设置奇数表示选择，偶数表示不选。再将已选的元素组合起来，得到所有组合。

大致流程图应该是这样（这里省略了“否”部分以及循环读取数组元素部分）按惯例贴上：

1. Function getCombin(ByRef arr() As Variant, ByVal num As Integer) As String
   
2.     Dim i As Integer
   
3.     Dim j As Integer
   
4.     Dim intTimes As Integer
   
5.     Dim intSelect As Integer
   
6.     Dim strResult As String
   
7.     '根据数组的上限设定循环次数。
   
8.     For i = 1 To 2 ^ (UBound(arr) + 1) - 1
   
9.     '初始化数据，intTimes视为循环次数编号。
   
10.         intTimes = i
    
11.     '每次循环完，将选择次数设置为0，组合字符串设置为空字符串。
    
12.         strResult = ""
    
13.         intSelect = 0
    
14.         '按数组构建循环。
    
15.         For j = LBound(arr) To UBound(arr)
    
16.         '奇数次数时表示已选，偶数次数时表示不选。
    
17.         '比如数组为（1，2，3）。那么i=1时选择1，i=2时不选1，i=3时选择2，i=4时不选2，如此类推。
    
18.             If intTimes Mod 2 = 1 Then
    
19.         '选中后，组合元素为字符串，并统计intSelect。
    
20.                 strResult = strResult & arr(j)
    
21.                 intSelect = intSelect + 1
    
22.             End If
    
23.         '除以2取整表示完成一轮的选择和不选。
    
24.             intTimes = intTimes \ 2
    
25.         Next j
    
26.         '如果选择元素个数和要求的个数相同
    
27.         If num = intSelect Then
    
28.         '初始化时设为strResult，之后再将结果进行拼接。
    
29.             If getCombin = "" Then
    
30.                 getCombin = strResult
    
31.             Else
    
32.                 getCombin = getCombin & "," & strResult
    
33.             End If
    
34.         End If
    
35.     Next i
    
36. End Function
    
37. 
    
38. 
    
39. Sub test()
    
40.     Dim arr() As Variant
    
41.     arr = Array(1, 2, 3, 4, 5)
    
42.     Dim n As Integer
    
43.     n = 3
    
44.     Dim output As String
    
45.     output = getCombin(arr, n)
    
46.     Debug.Print output
    
47. End Sub

复制代码

最后奉上附件。


【新手进阶】之一：If分支语句
【新手进阶】之二：分支语句总结
【新手进阶】之三：循环语句For
【新手进阶】之四：循环语句Do和死循环
【新手进阶】之五：递归算法
【新手进阶】之六：冒泡排序
【新手进阶】之七：从四脚腾空的奔马谈起——原来界面可以这样设计
【新手进阶】之八：公共变量与传址过程、传值过程
【新手进阶】之九：仓库管理系统
【新手进阶】之十：从百钱百鸡谈起——浅谈“规划求解”兼答lingjiang问
【新手进阶】之十一：“庖丁解牛”和“纪昌学射”——浅谈表格式文本数据的导入
【新手进阶】之十二：嵌套与并列——再谈If流程问题
【新手进阶】之十三：记录集的“凌迟”——逐条导出记录集
【新手进阶】之十四：“不明觉厉”——浅谈左侧导航栏的设计
【新手进阶】之十五：浅谈ADO之序言
【新手进阶】之十六：浅谈ADO之Connection
【新手进阶】之十七：浅谈ADO之Conmmand（上）
【新手进阶】之十八：浅谈ADO之Command（下）
【新手进阶】之十九：Outlook风格导航界面
【新手进阶】之二十：浅谈ADO之Recordset（上）
【新手进阶】之二十一：浅谈ADO之Recordset（下）
【新手进阶】之二十二：浅谈不绑定数据源操作记录

roych

附上该版友原有代码（修正了一些bug）

1. Public Sub ListCombinations(n As Integer, m As Integer)
   
2.     Dim a() As Variant
   
3.     ReDim a(1 To m)
   
4.     Combination 1, n, a, 1, m
   
5. End Sub
   
6. Private Sub Combination(t As Integer, n As Integer, a() As Variant, k As Integer, m As Integer)
   
7.     Dim i As Integer
   
8.     If k > m Then
   
9.         Debug.Print Join(a, " ")
   
10.         Exit Sub
    
11.     End If
    
12.     For i = t To n
    
13.         a(k) = i
    
14.         Combination i + 1, n, a, k + 1, m
    
15.     Next i
    
16. End Sub
    
17. 
    
18. 
    
19. Sub test()
    
20.     ListCombinations 5, 3
    
21. End Sub

复制代码

相对简洁，不过仅限于数值。如需持久化（比如写入数据表或者文件），可能需要修改主函数。里面使用递归算法是代码中的点睛之笔。