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

彭希仁

任意M个数字，对它们进行N个数的排列组合，并全部显示出来.COMBIN（M，N)

星期天白天睡多了,搞得我晚上失眠,无聊之中冒出以下排列组合的算法.

一般算法

Sub pengxi()
    aa = Timer
    Dim x%
    Dim i%
    Dim j%
    Dim jj As Long
    a = [A65536].End(xlUp).Row + 1
    arr = Range("A1:A" & a)
    z = Cells(1, 2)
    ReDim arr1(1 To z + 1) As Long   '存地址
    ReDim arr2(1 To z + 1)   '存组合
   
    Open "d:\peng.txt" For Output As #1
    For i = z To 1 Step -1    '初始化
        arr1(i) = i
        arr2(i) = arr2(i + 1) & " " & arr(i, 1)
    Next i
    arr1(z + 1) = 1000
    Do
        jj = jj + 1                   '输出结果
     Print #1, arr2(1)

        For i = 1 To z
            If arr1(i + 1) - arr1(i) > 1 Then Exit For
        Next i

        arr1(i) = arr1(i) + 1
        arr2(i) = arr2(i + 1) & " " & arr(arr1(i), 1)

        For j = i - 1 To 1 Step -1
            arr1(j) = j
            arr2(j) = arr2(j + 1) & " " & arr(j, 1)
        Next j
    Loop While arr1(z) < a
    Close #1
    MsgBox "找到 " & jj & " 个解! 花费" & Format(Timer - aa, "0.00" & "保存在D:\peng.txt") & "秒"
End Sub
递归算法

Sub peng()
    aa = Timer
    Dim jj As Long, cc As Long
    Open "d:\peng.txt" For Output As #1
    arr = Range("A1:A" & [A65536].End(xlUp).Row)
    Call xi("", arr, 1, 0, Cells(1, 2), jj)
    Close #1
    MsgBox "找到 " & jj & " 个解! 花费" & Format(Timer - aa, "0.00" & "保存在D:\peng.txt") & "秒"
End Sub

Sub xi(a, arr, x As Long, y As Long, z As Long, jj As Long)
    If y = z Then
        jj = jj + 1
        Print #1, a
        Exit Sub
    End If
    If x = UBound(arr) + 1 Then Exit Sub
    If y + UBound(arr) - x + 1 < z Then Exit Sub
    Call xi(a & " " & arr(x, 1), arr, x + 1, y + 1, z, jj)  '字附串和数字的处理速度是相差很大的
    Call xi(a, arr, x + 1, y, z, jj)
End Sub

LrTBjr9k.rar (10.65 KB, 下载次数: 2169)

2007-11-12 16:39 上传

点击文件名下载附件
[讨论]排列组合之最优算法

[此贴子已经被作者于2007-11-12 16:39:48编辑过]

hhzjxss

厉害厉害，彭希仁又出新作品了！

彭希仁

以上解法,递归算法比一般算法要慢20%左右,是递归本身的先天不足所引起的(程序在调用下一个过程的时候程序会把当然所有的变量先存起来,会占用时间).可通过披上羊皮来弥补不足.

当然以上两种算法实现的原理是不一样的

递归用的是二进制\剪枝原理.

而一般算法用的原理我也说不上来是什么.有点象搬箱子吧

hhzjxss

递归算法还没学过呢！

northwolves

学习

TGB

俺也收下学习！
连狼版都要向你学习，可见有多高了！



不过有一点你要向我学习的是怎么打MM的望^_^，我看你好像也是发现了点什么........

彭希仁

QUOTE:

以下是引用TGB在2007-11-12 20:23:12的发言：
俺也收下学习！
连狼版都要向你学习，可见有多高了！



不过有一点你要向我学习的是怎么打MM的望^_^，我看你好像也是发现了点什么........

呵呵,这MM是我女儿.很可爱吧.

minjiwei

谢了，楼主。

TGB

原来是彭兄的女儿（我还以为是男孩），真的好可爱！

这么看来，我比你虚长了，我女儿读初二了。

看来我们都只有当外公的命了——当不成爷爷了，哈哈哈哈

泓()

TGB，厉害．我认为彭老师，小时候的照片．