怎样一步步学排列组合

liuguansky · 发表于 2012-11-23 14:53

向吴

姐学习.

香川群子 · 发表于 2012-11-23 15:33

爱疯发表于 2012-11-23 11:57
谢谢群子老师给的例子

14,16楼是咋想出来的呀？

本质上就是要熟悉VBA数组的结构、存取方法。（行、列索引的计算转换）

以及，各种循环的作用for……next，do……loop等，

以及在循环中有效使用if……then判断语句。

…………总之，技术问题实际上并不难，但是要能灵活组织起来，用到活起来。

…………
至于思路，那就靠下面几条路：
1. 自己碰到问题以后，用心专研。
找到一个解决方法以后，自己继续钻研是否还有其它更好的思路、更好的解决办法。
在此过程中，即使没有得到更好的结果，也会有经验的积累。

2. 学习别人的现成的好的代码，研究其思路、作用和局限性。

3. 和别人交流。相互学习。

香川群子 · 发表于 2012-11-23 16:09

本帖最后由香川群子于 2012-11-23 16:12 编辑

对2楼Miss wcy 吴姐代码的进一步解释：

Sub 组合()
      Dim i%, n% , m%
      n = 5: m = 3 '指定组合参数

      ReDim a%(1 To m) '定义一维数组a，用来保存每次组合结果的状态
      For i = 1 To m
         a(i) = i '组合状态初始化→ 如： 1,2,3
      Next

   i = m '组合完成状态个数i，初始值=m
   Do
         If i = m Then Debug.Print Join(a, " ") '仅当组合完成状态个数=m时需要输出组合结果
         '>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
         '下面开始循环，让末位以及各个i位置递增，并检查是否超上界限。
            If a(i) < n-m+i Then '如果当前位值 < 上界 n-m+i （如 3,4,5）时可以继续递增。

                  a(i) = a(i) + 1 '当前位递增，以便生成下一个不同状态的组合

                  If i < m Then '如果当前位置不是末位n那么需要检查剩余状态位。
                     '从当前位之后(i+1)起，检查直到末位(m)，使之成为连续递增如 2,3,4
                     For j = i+1 To m
                           a(j) = a(j-1) + 1 '从当前位之后开始，向当前位看齐！
                        Next
                        i=m '循环结束后，即完成了一个新的台阶状态，必须使i又=m
                  Else
                        '如果当前位仍然是末位m，那么不需要检查。直接进入下一组合
                  End If

            Else '如果当前位已经超出界限 n-m+i ，那么需要检查前面低位的状态了。
                  i = i - 1 '检查指针i-1，以便下一次do……loop循环从前面低位开始检查
            End If
         '<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
   Loop Until i = 0
End Sub

我把吴姐的代码改了一下，其中有些语句实际上是多余的，或者变成了较低效率的。
但是，这样可以更方便其它人对算法进行彻底、透彻地去理解。

香川群子 · 发表于 2012-11-23 16:15

其中，蓝色字体部分的if……else……endif 判断是多余的。

因为直接走其中红色字体部分的for……next循环，并不会产生错误和多余的计算。

但是这样一写，就更方便理解了。

香川群子 · 发表于 2012-11-23 16:31

红色字体部分，我故意这样写了。

For j = i+1 To m
a(j) = a(j-1) + 1 '从当前位之后开始，向当前位看齐！
Next
i=m '循环结束后，即完成了一个新的台阶状态，必须使i又=m

和吴姐原代码比较：
For i = i To m - 1
a(i + 1) = a(i) + 1
Next

显然吴姐的代码更高效……不用到最后再对i赋值=m

具体状态例如：

状态： 1,2,5
检查 i=3时a(3)=5,而上界=n-m+i=5-3+3=5
即 a(i)<n-m+i不成立，当前位不可继续递增下去了，
于是要检查前面低位i=i-1=2

接下来，检查i=2时a(2)=2<n-m+i=4，可以递增
于是，a(2)=a(2)+1=3
接着进入For i = i To m - 1 循环，即For i = 2 To 2循环一次
则发现 a(i+1)=a(3)需要阶梯递增，a(3)=a(2)+1=4
最后就得到了新的组合： 1,3,4

…………

状态： 1,4,5
检查 i=3时a(3)=5,而上界=n-m+i=5-3+3=5
即 a(i)<n-m+i不成立，当前位不可继续递增下去了，
于是要检查前面低位i=i-1=2

接下来，检查i=2时a(2)=4，,而上界=n-m+i=5-3+2=4
即 a(i)<n-m+i不成立，当前位也不可继续递增下去了，
于是要检查前面低位i=i-1=2-1=1

接下来，检查i=1时a(1)=1，<n-m+i=3，可以递增
于是，a(1)=a(1)+1=2
接着进入For i = i To m - 1 循环，即For i = 1 To 2要循环二次
则发现 a(i+1)=a(2)需要阶梯递增，a(2)=a(1)+1=3
接下来 a(i+1)=a(3)也需要阶梯递增，a(3)=a(2)+1=4

最后就得到了新的组合： 2,3,4

这样写大家更好理解一些。

爱疯 · 发表于 2012-11-23 17:44

谢谢群子老师！

我不解的主要就是红色部分：为什么要“这样”设计？
而要解释为什么，又将是说明一个纯数学的证明题，不知道自己还能理解么

香川群子 · 发表于 2012-11-26 14:48

wcymiss 发表于 2012-11-17 01:45
1、数学中常用的是n是总数，m是选取数。
2、排列组合是经典问题，代码一般也比较程式化。下面的代码应该是 ...

2楼吴姐do……loop循环代码很简洁高效，
我改成了可以根据外部数据生成组合结果的实用性代码:

Sub GetCombin_wcy()
tms = Timer
Dim i%, j%, s&, t$
'原始数据放置在A1开始的A列中。
n = [a1].End(4).Row '获取原始数据个数（A列最大行数）
sj = [a1].Resize(n) '原始数据各元素读入数组sj
m = [b1] 'B1单元格中写入需要抽取的元素个数
ReDim a%(1 To m) '数组a用来存放各个数位的当前组合状态
' ReDim b%(1 To m) '这个存放上界值的数组可以省略不用，以后在代码中直接计算得到。
'以下为数组a初始化，存入1,2,3,4……
'以及把组合最终结果（根据原始数据相应转换后的结果）存入字符变量t
a(1) = 1
If m > 1 Then t = sj(1, 1) Else t = ""
For i = 2 To m - 1
a(i) = i
t = t & ";" & sj(i, 1)
Next
a(m) = m
s = WorksheetFunction.Combin(n, m) '计算组合结果总数
ReDim jg(1 To s, 1 To 1) '定义相应大小的存放结果的数组
k = 1 '当前组合结果数初始化
i = m '循环指针初始化，从末位开始
Do
If i = m Then '如果参与组合的元素个数达到m个即可输出本次组合结果
' Debug.Print Join(a, " ") '代码调试时可以观察到组合变换。
jg(k, 1) = t & ";" & sj(a(m), 1) '本次组合的文本字符串结果存入jg数组
'（算法是1~m-1的组合结果t，加上当前末位指针所指元素）
k = k + 1 '组合结果数递增1 (仅仅为了能够依次把组合结果存入数组jg中去)
End If
If a(i) < n - m + i Then '检查各数位是否可以递增1，以便生成新的组合结果
a(i) = a(i) + 1 '可以递增时直接递增即可。
If i < m Then '如果本数位i不是末位m，那么除了本数位递增1以外，其余后面各位还要阶梯递增对齐
For i = i To m - 1 '这里写成i to m-1，而实际做的是 i+1 to m
a(i + 1) = a(i) + 1 '实际循环结果，是从本位+1开始直到末位，全部向前位+1对齐
Next
'以上为止是对各个数位的序列状态进行组合变化，结果存放在数组a中，如 1,2,3；3,4,6等
'但需要通过下面几句代码，把组合序号对应的原始数据元素取出。
t = sj(a(1), 1) '字符变量t中存入组合第一位序号a(1)对应元素,如a(1)=3就取第3个元素。
For j = 2 To m - 1
t = t & ";" & sj(a(j), 1) '循环从第2数位直到m-1数位，结果依次取出合并到字符变量t中
Next
End If
Else '当检查该数位不可以递增1时
i = i - 1 '数位指针i-1处理，以便进入下一次循环检查前面i-1数位位置的状态是否可以递增……
End If
Loop Until i = 0 '重复do……loop循环直至检查到i=0，即i=1也不能递增时，结束循环。
MsgBox k - 1 & vbCr & Format(Timer - tms, "0.000s") '输出组合结果总数，以及组合算法耗用时间
'以下为输出所有组合结果到工作表
tms = Timer
[d:d] = ""
[d1].Resize(s) = jg
[d1].EntireColumn.AutoFit
MsgBox Format(Timer - tms, "0.000s")
End Sub

复制代码

		自动登录	找回密码
密码			注册

怎样一步步学排列组合

评分