[讨论]排列组合之最优算法

robinob

无限痛苦中…好几次眼看已经有了方法～恩～还望彭版再给指指

robinob

QUOTE:
以下是引用hulu456123在2007-12-2 2:26:56的发言：

精确到小数点后两位可以吗？

总是死机…………

Private arr(1 To 200), arr1, j, z, k, bb
Private arr3(1 To 65536, 1 To 1)

Sub cai()
Application.ScreenUpdating = False
aa = Timer
Columns("A:A").Select
Selection.Sort Key1:=Range("A1"), Order1:=xlAscending, Header:=xlGuess, _
        OrderCustom:=1, MatchCase:=False, Orientation:=xlTopToBottom, SortMethod _
        :=xlPinYin
Range("C:i") = ""
z = [A65536].End(xlUp).Row
arr1 = Range("a1", Cells(z, 1))

For i = z To 1 Step -1
arr(i) = arr(i + 1) + arr1(i, 1)
Next i

j = 0
k = Cells(1, 2)
bb = 0

lj 1, k, ""

Range(Cells(1, 3 + bb), Cells(j, 3 + bb)) = arr3
MsgBox "找到 " & bb * 65536 + j & " 个解! 花费" & Format(Timer - aa, "0.00") & "秒"
End Sub
Sub lj(i, x, y$)
If x >= arr1(i, 1) And x <= arr(i) Then
   If x = arr1(i, 1) Then
    If j = 65536 Then
      Range(Cells(1, 3 + bb), Cells(j, 3 + bb)) = arr3
      j = 1
      bb = bb + 1
    Else
      j = j + 1
    End If
    arr3(j, 1) = y & arr1(i, 1) & "=" & k
   Else
    If i < z Then
       If x >= 2 * arr1(i, 1) Then lj i + 1, x - arr1(i, 1), y & arr1(i, 1) & "+"
       lj i + 1, x, y
    End If
   End If
End If
End Sub

我用的老师的这个程序，然后运行报错
Range(Cells(1, 3 + bb), Cells(j, 3 + bb)) = arr3

怎么处理～

robinob

我样本用的还是我举例的那些数字

彭希仁

小数都乘以10N次方,不就是整数了吗

robinob

太过纠结居然没想到这个办法……额………………………………

robinob

我用118那个算……提示溢出……

robinob

老师好～我周末出差了～回来继续企盼中～老师抽空再给诊断诊断～

raulerini

彭版的代码中，递归部分果然是十分精妙，我等PFPF。
但是，彭版的变量定义的较为随意，阅读起来难以理解，并且递归部分写得较为晦涩（尽管递归本来就是一个很晦涩的东东）
我在不甚理解的基础上，稍加整理，加上了一部分我自己的理解，也能达到递归的效果，希望能助于更多人理解。
也请彭版多多指教

'下面的代码中，结果字符串表示最终生成的一组组合的结果表达式,选择位数表示从一组数据中取数时，当前的取值在该数组中的位置，已取值数量表示已经从该数组中取的元素的个数，数组大小和共需选数量分别代表M取N组合中的M和N
'彭版的代码利用的是顺序取数的方法（至少我这么认为），也就是取了第二位数后，后面的取数不能再反过来取第二位前面的数，即只允许生成1，2，3的一组数，不能生成2，1，3的这样一组数
Public 结果字符串$, 选择位数%, 已取值数量%, 共需选数量%, 数组大小%
Public 元素数组
Sub 组合(结果字符串$, 取值位数%, 已取值数量%)
    If 已取值数量 = 共需选数量 Then
        Range("C65536").End(xlUp).Offset(1) = 结果字符串
        Exit Sub
    End If
    If 取值位数 <= 数组大小 - (共需选数量 - (已取值数量 + 1)) Then
            '递归循环的条件是：当前的取值位数，不超过数组的总大小减去剩余可取值的数量(即 共需选数量 - (已取值数量+1)，其中已取值数量+1代表的是当前的位数取过之后，已经取值的总个数)
            '例如1-8中选5个数，数组大小为8，共需选数量为5，则对于第3位数,已取值数量=2，已取值数量+1=3代表的就是当前取值位数3，
            '当前的取值位数<=数组大小 - (共需选数量 - (已取值数量 + 1)) =8-(5-(2+1))=6,即第三位数最多只能选数字6，因为如果第3位选7了话，后面剩余的第4位和第5位只有一个8可以取，那么就不足取了     
             组合 结果字符串 & " " & 元素数组(取值位数, 1), 取值位数 + 1, 已取值数量 + 1
                     '这一次递归调用的单个组合中的所有元素，即生成其中某一个组合，原理是利用递归循环，依次从数组M中选出N个数来
            '例如6选3，依次会生成1,12,123,当已选数量=3时候退出这一次递归
            组合 结果字符串, 取值位数 + 1, 已取值数量
            '这一递归调用所有可能生成的组合，即当上面的递归已经满足选择了3个元素的时候，退出上面的递归，并将起始的取值位数向后移动一位
            '例如6选3，当上面已经生成了123一组数时，满足了退出上一个递归的条件，则将原有的取值位数+1，经过上面的递归，从栈中第一个弹出的取值位数=3 ，向后移动一位，则取值位数为4，'这样，就成功取到了1,2,4一组数
            '可以这样理解，第一个递归是单个组合内部横向取数，第二个递归是生成所有组合，即纵向取数
End If
End Sub

Sub main()
Range("C:C").Clear
数组大小 = [A65536].End(xlUp).Row
元素数组 = Range("A1:A" & 数组大小).Value
共需选数量 = [B1]
[C1] = "组合"
组合 "", 1, 0
End Sub

简化了一下代码，少了一些不必要的变量，本想做个flash来帮助理解，可惜不会。
彭版自己所阐述的太极一生二原理，我始终没能理解。不知道我自己上面的理解能不能得到认同。 递归求组合.rar (9.28 KB, 下载次数: 73)

2010-7-26 09:42 上传

点击文件名下载附件

[ 本帖最后由 raulerini 于 2010-7-26 09:56 编辑 ]

zz5151353

雖然沒用到,留下腳印,有空再回來學習了 !!!

坚持到底

彭老师你好，请问能不能优化一下，A列的数字能不重复吗？