怎样一步步学排列组合

爱疯 · 发表于 2012-11-16 23:40

'求组合：从n个不同元素中，任取m(m≤n）个元素
Sub test()
Dim arr() '数据源
Dim n, m
Dim a, b, c '循环变量名
'COMBIN(n,m)=m!/((m-n)!n!)
n = 5
m = 3
'COMBIN(5,3)=5!/(2!*3!)=120/(2*6)=10
'实例中，很可能不是从1开始的n个自然数，而是一个区域
ReDim arr(1 To n)
For a = 1 To n
arr(a) = a
Next a
'循环特点：
'1）m层循环
'2）从外到内，初值从LBound(arr)开始，逐层+1
'3）从内到外，终值从UBound(arr)开始，逐层-1
For a = 1 To 3
For b = a + 1 To 4
For c = b + 1 To 5
Debug.Print arr(a); arr(b); arr(c)
Next c
Next b
Next a
End Sub

复制代码

我现在只会这么来“解决”组合问题。显然，不但通用性很差，还是半自动的。
这是群子老师提供的自动生成的代码：http://www.excelpx.com/thread-289661-1-1.html 13#
下面或许有很多相关问题，希望群子老师和高手们多多指导！

问1：群子老师示例和百度的，m,n的定义相反。数学中或最普遍的描述应是哪种？
问2：对于组合问题，自1#这种方法后，新手最适合、最应当掌握的是哪种方法呀？
如果群子老师发过，是哪帖的几楼呀。

谢谢！
PS：本帖不设最佳，只为多学习点

wcymiss · 发表于 2012-11-17 01:45

1、数学中常用的是n是总数，m是选取数。
2、排列组合是经典问题，代码一般也比较程式化。下面的代码应该是比较效率和通用的：

Sub 组合()
Const n As Integer = 5, m As Integer = 3
Dim i As Integer, a(1 To m), b(1 To m) As Integer
For i = 1 To m '生成组合和上界值
a(i) = i
b(i) = n - m + i
Next
i = m
Do
If i = m Then Debug.Print Join(a, " ") '输出组合序列
If a(i) < b(i) Then '从最后递增1，产生新序列
a(i) = a(i) + 1
If i < m Then
For i = i To m - 1
a(i + 1) = a(i) + 1
Next
End If
Else
i = i - 1
End If
Loop Until i = 0
End Sub

复制代码

至于你说的“实例”，只要把它装入一维数组内，然后根据上述代码产生的组合的提取此数组内对应位置的元素即可。

hwc2ycy · 发表于 2012-11-17 09:49

排队。

9910343 · 发表于 2012-11-17 12:31

学习学习学习下学习

爱疯 · 发表于 2012-11-17 15:27

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

谢谢wcymiss!

QQ截图未命名.jpg

问1：当n=5,m=3时，b(1)、b(2)、b(3)，在图中有对应单元格吗？如果有，是那个。
问2：可否将2楼的代码，转为步骤说明。
因为自己还是不理解为什么要这么写，希望能理解这些公式是怎么求来的。

爱疯 · 发表于 2012-11-17 16:20

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

Sub 组合()
Const n As Integer = 5, m As Integer = 3
Dim i As Integer, a(1 To m), b(1 To m) As Integer
For i = 1 To m '生成组合和上界值
      a(i) = i
      b(i) = n - m + i
Next
i = m
Do
      If i = m Then Debug.Print Join(a, " ") '输出组合序列
      If a(i) < b(i) Then '从最后递增1，产生新序列
         a(i) = a(i) + 1
'          If i < m Then
            For i = i To m - 1
                  a(i + 1) = a(i) + 1
            Next
'          End If
      Else
         i = i - 1
      End If
Loop Until i = 0
End Sub

我发现注释掉这IF后，结果还是一样？可以取消么

wcymiss · 发表于 2012-11-17 16:26

每次的组合是存放在a(1)、a(2)、a(3)里的，a(1)的取值范围是1至3，a(2)的取值范围是2-4，a(3)的取值范围是3-5，b(1)、b(2)、b(3)就分别是a(1)、a(2)、a(3)的取值的最大值。

b数组在代码里一旦赋值后就固定不变，有变化的是i值和a数组的值。只要在本地窗口查看下它们的变化就能理解了：
每次对最右边的数字进行加1，一旦加到上限则往左偏移一位进行加1，同时也重新处理其后位置的每一个数。
如5选3：
1、先生成1 2 3
2、最右边的3加1：1 2 4
3、4未到上限5，再加1：1 2 5
4、到上限5了，i = i - 1，把第2个数字“2” 加1，同时第3个数字也对应改变（在第二个数字上加1）：1 3 4
5、最右的数字未达上限5，加1：1 3 5
……

还理解不了的话就死记硬背吧。。。。反正也没几句代码

爱疯 · 发表于 2012-11-17 17:24

2楼代码难理解的是do loop

do loop中难理解的是if

if中难理解的是for next

....

让我自己去想，是怎么也想不出来这么做的，

刚好结果是对的，这不科学啊

{:241:}

wcymiss · 发表于 2012-11-17 17:38

爱疯发表于 2012-11-17 16:20
Sub 组合()
Const n As Integer = 5, m As Integer = 3
Dim i As Integer, a(1 To m), b(1 To ...

可以，我忘了for的特性了，多写了一层判断

爱疯 · 发表于 2012-11-17 17:49

wcymiss 发表于 2012-11-17 17:38
可以，我忘了for的特性了，多写了一层判断

哦。
2楼代码含义好懂。可为什么这样循环，就理解不了了。
虽然加了点注释，可还是不理解。是不是要用什么数学方法才好证明。真不想这样硬记代码呀
{:141:}

Sub 组合()
Const n As Integer = 5, m As Integer = 3
Dim i As Integer, a(1 To m), b(1 To m) As Integer
'生成组合和上界值
For i = 1 To m
a(i) = i
b(i) = n - m + i
Next
i = m
Do
'因为 i < m 时的修改都被忽略，所以不必输出
If i = m Then Debug.Print Join(a, " ")
'>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
'如果当前位 < 上界
If a(i) < b(i) Then
a(i) = a(i) + 1 '修改当前位，生成下一个组合
'忽略范围从当前位(i)起，到倒数第2(m-1)位，
For i = i To m - 1
'与a(i) = a(i) + 1同理，只不过修改的对象可能有多个
a(i + 1) = a(i) + 1
Next
'循环结束后，i又=m了
Else
i = i - 1
'开始最外层的下一次循环
'上界值标准，也变了
End If
'<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Loop Until i = 0
End Sub

复制代码

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

怎样一步步学排列组合

相关帖子