遍历组合算法的模块化

在日常的需求设计中，遍历组合是一个常见的问题。

　　例如：现在有N个不同的数。要求在其中找到M个数，使得M个数之和为指定的S，求所有满足条件的组合。

　　这是一个很明显的遍历组合的问题。一般采用递推算法，求出满足条件的解。

　　这类问题一般都采用一个数组P，来存放解。遍历整个组合空间，来找出解（有可能是所有解、也可能是一个解，根据题目要求来定）

　　由于这类问题解法是固定的，故在此把该算法模块化。留待日后查阅用。

　　上图是该算法的算法流程图

　　下面贴出该算法的伪代码，用的是VB2005

1. Public Sub Traversal() 
2. 　　　　Dim P() As Integer, K As Integer, IsGroup As Boolean 
3. 　　　　InitData()　　　　　　　　　　　　　　　　　　　　　　　　注：初始化数组代码块 
4. 　　　　K = P.GetUpperBound(0) 
5. 　　　　Do 
6. 　　　　　　If IsMatch()  Then　　　　　　　　　　　　　　　　　　注：判别是否满足条件的代码块 
7. 　　　　　　　　OutputAnswer()  　　　　　　　　　　　　　　　　注：输出解的代码块 
8. 　　　　　　End If 
9. 　　　　　　IsGroup = False 
10. 　　　　　　Do 
11. 　　　　　　　　Delta(K)　　　　　　　　　　　　　　　　　　　　　注：P(K)自增加值的代码块 
12. 　　　　　　　　Do 
13. 　　　　　　　　　　If Overflow(K) Then　　　　　　　　　　　　　注：判断P(K)是否越界的代码块 
14. 　　　　　　　　　　　　K = K - 1 
15. 　　　　　　　　　　　　Exit Do 
16. 　　　　　　　　　　Else 
17. 　　　　　　　　　　　　If K < P.GetUpperBound(0) Then 
18. 　　　　　　　　　　　　　　K = K + 1 
19. 　　　　　　　　　　　　　　SetP(K)　　　　　　　　　　　　　　　 注：依据条件设置P(K)值的代码块 
20. 　　　　　　　　　　　　Else 
21. 　　　　　　　　　　　　　　IsGroup = True 
22. 　　　　　　　　　　　　　　Exit Do 
23. 　　　　　　　　　　　　End If 
24. 　　　　　　　　　　End If 
25. 　　　　　　　　Loop 
26. 　　　　　　Loop Until (K < 0 Or IsGroup = True) 
27. 　　　　Loop Until K < 0 
28. 　　　　SomeEndCode()　　　　　　　　　　　　　　　　　　　　　 注：求解结束的代码块 
29. 　　End Sub 

举例说明：有1、4、7、2、5、6、9、8、7、5十个数，求四个数之和为20的所有组合。
　　分别阐述各个代码块的实现
　　初始化数组代码块：

1. Dim N() As Integer={1,4,7,2,5,6,9,8,7,5} 
2. 　　　　Redim P(3) 
3. 　　　　P(0)=0:P(1)=1:P(2)=2:P(3)=3 

判别是否满足条件的代码块：

1. N(P(0))+N(P(1))+N(P(2))+N(P(3))=20 

输出解的代码块：

1. Debug.Print N(P(0)) & "," & N(P(1)) & "," & N(P(2)) & "," & N(P(3)) 

P(K)自增加值的代码块：

1. P(K)=P(K)+1 

　判断P(K)是否越界的代码块：

1. P(K)>K+6 

依据条件设置P(K)值的代码块：

1. P(K)=P(K-1)+1 

求解结束的代码块
　　　　本题没必要设置这段代码

　　故本题的代码如下：

1. Public Sub Traversal() 
2. 　　　　Dim P() As Integer, K As Integer, IsGroup As Boolean 
3. 　　　　Dim N() As Integer={1,4,7,2,5,6,9,8,7,5} 
4. 　　　　Redim P(3) 
5. 　　　　P(0)=0:P(1)=1:P(2)=2:P(3)=3 
6. 　　　　K = P.GetUpperBound(0) 
7. 　　　　Do 
8. 　　　　　　If N(P(0))+N(P(1))+N(P(2))+N(P(3))=20  Then　　　　　　　 
9. 　　　　　　　　Debug.Print N(P(0)) & "," & N(P(1)) & "," & N(P(2)) & "," & N(P(3)) 
10. 　　　　　　End If 
11. 　　　　　　IsGroup = False 
12. 　　　　　　Do 
13. 　　　　　　　　P(K)=P(K)+1 
14. 　　　　　　　　Do 
15. 　　　　　　　　　　If P(K)>K+6 Then　　 
16. 　　　　　　　　　　　　K = K - 1 
17. 　　　　　　　　　　　　Exit Do 
18. 　　　　　　　　　　Else 
19. 　　　　　　　　　　　　If K < P.GetUpperBound(0) Then 
20. 　　　　　　　　　　　　　　K = K + 1 
21. 　　　　　　　　　　　　　　P(K)=P(K-1)+1 
22. 　　　　　　　　　　　　Else 
23. 　　　　　　　　　　　　　　IsGroup = True 
24. 　　　　　　　　　　　　　　Exit Do 
25. 　　　　　　　　　　　　End If 
26. 　　　　　　　　　　End If 
27. 　　　　　　　　Loop 
28. 　　　　　　Loop Until (K < 0 Or IsGroup = True) 
29. 　　　　Loop Until K < 0 
30. 　　End Sub 

把这类问题模块化，以后碰到类似的问题。直接修改各个代码块的代码。

　　着文以记之。