求排列组合结果的自定义函数

香川群子 · 发表于 2011-6-17 14:04

从m个元素中取n个，产生各种不同的排列……

现在想知道所有排列结果中，第n个位置的具体排列结果，
而不需要事先排出所有结果，则可以使用下述自定义函数。

Function PN(Rng As Range, n, k, Optional InsertWd = "") '给出第k个位置的排列结果
m = Rng.Count '元素数
PAM = Application.WorksheetFunction.Permut(m, n)
If k > PAM Then PN = "> " & PAM: Exit Function '检查k值如果大于可能排列结果，则终止并提示。
Dim s As New Collection '把所有元素加入集合s中待用。
For i = 1 To m
s.Add Rng.Cells(i)
Next
For i = 1 To n - 1 ’按顺序取n-1个值
j = Int((k - 1) / Application.WorksheetFunction.Permut(m - i, n - i)) Mod (m - i + 1) + 1
'求k位置序号，按排列值分割以后，再按待排列数，求余转换为序数值，即可从s集合中得到该元素
'例如：8取4时共1680个排列组合，
'首先，第1位的排列数应该是按照P(7,3)=210，即8个元素每一个有210种。210 x 8 =1680
'接下来，第2位的排列数应该是按照P(6,2)=30，即7个元素每一个有30种。30 x 7 =210
'接下来，第3位的排列数应该是按照P(5,1)=5，即6个元素每一个有5种。5 x 6 =30
'以此类推，直至倒数第2位结束，因为最后一位的算法不一样的。
PN = PN & s(j) & InsertWd '逐个加入选定元素，并插入分割符号。(默认为空格)
s.Remove j '从集合s中去掉已经使用过的元素
Next
'最后一位，是k位置序号对于剩余数的余数，例如，8取4时取好3个剩最后一位时，还剩5个元素可选
PN = PN & s((k - 1) Mod (m - n + 1) + 1)
End Function

复制代码

请看附件。

香川群子 · 发表于 2011-6-17 14:13

有了上面这个函数，那么求m个元素取n个时的全部排列组合结果，
也可以简单地、通用性地，以下面这样的代码来求所有结果，
而不必考虑m、n值不同时，写循环代码的层数要增加了。

当然，如果使用递归迭代方式的话，也是可以的。
速度或许更快。

Sub PLtest()
Dim Rng As Range
Set Rng = Selection
m = Rng.Count
n = m
InsertWd = "-"
PAM = Application.WorksheetFunction.Permut(m, n)
ReDim d(PAM, n)
d(0, 0) = "No"
d(0, 1) = "PL"
For i = 1 To PAM
d(i, 0) = i
d(i, 1) = PN(Rng, n, i, InsertWd)
Next
ActiveCell.Offset(5, 0).Resize(PAM + 1, 2) = d
End Sub

复制代码

这里的代码，是把排列元素横向排在同一列中处理的。

香川群子 · 发表于 2011-6-23 08:00

求任意序号位置组合结果的自定义函数也已经编写好了：

Function CN(Rng As Range, n, k, Optional InsertWd = "")
m = Rng.Count
CAM = Application.WorksheetFunction.Combin(m, n) '计算最大组合数
If k > CAM + 0.1 Then CN = "> " & CAM: Exit Function
Dim s As New Collection
For i = 1 To m
s.Add Rng.Cells(i) '集合s中加入组合对象元素
Next
For i = 1 To n - 1
For j = 1 To m - n + 1
t = Application.WorksheetFunction.Combin(m - i - p, m - n - p) '按组合公式排列
If k > t + 0.1 Then
k = k - t
p = p + 1
Else
l = l + j
Exit For
End If
Next
CN = CN & s(l) & InsertWd
Next
CN = CN & s((k - 1) Mod (m - l + 1) + l + 1) '最后一位的组合结果可以直接求余计算。
End Function

复制代码

cumulonimbus · 发表于 2011-7-7 08:08

群子小姐，你好，有一程序想不明白，能否详加解释，谢谢
j = Int((k - 1) / Application.WorksheetFunction.Permut(m - i, n - i)) Mod (m - i + 1) + 1
这个看了半天，也没明白，为什么是这个位置呢？

香川群子 · 发表于 2011-7-7 12:16

前面已经有解释了呀。

'求k位置序号，按排列值分割以后，再按待排列数，求余转换为序数值，
即可从s集合中得到该元素

'例如：8取4时共1680个排列组合，

'首先，第1位的排列数应该是按照P(7,3)=210，即8个元素每一个有210种。
210 x 8 =1680

j指的是通过计算定下来的元素序号。
j = Int((k - 1) / Application.WorksheetFunction.Permut(m - i, n - i)) Mod (m - i + 1) + 1

在这里：
m是组合总元素数=8，n是排列抽取数=4，
i指的是排列抽取次数=1
Application.WorksheetFunction.Permut(m - i, n - i)是指用Exce内置公式求排列值。
即相当于计算 P(m-i,n-i) 的结果，P(8-1,4-1)=P(7,3)=210

接下来，这样理解：
把1680个组合结果按照P(7,3)=210，即210个序号一组分区，
则可以得到8个分区，分别对应于1到8个元素。

具体做法是，对于求值序号参数k，按(k-1) / 210求整数的结果，
得到0-7之间的值，对应第0-7号元素。

下面以此类推。

'接下来，第2位的排列数应该是按照P(6,2)=30，即7个元素每一个有30种。30 x 7 =210

'接下来，第3位的排列数应该是按照P(5,1)=5，即6个元素每一个有5种。5 x 6 =30

…………

cumulonimbus · 发表于 2011-7-7 20:04

j = Int((k - 1) / Application.WorksheetFunction.Permut(m - i, n - i)) Mod (m - i + 1) + 1
这个前面的好理解，Int((k - 1) / Application.WorksheetFunction.Permut(m - i, n - i)) 就是你解释的意思，那后面加上这个求余数Mod (m - i + 1) + 1，要怎么解释呢？
谢谢，阿里亚多！

[ 本帖最后由 cumulonimbus 于 2011-7-7 20:05 编辑 ]

香川群子 · 发表于 2011-7-7 22:13

后面的求余计算是因为，每计算完一次，剩余元素数量就减少一个。

所以，是m-i+1

通过求余的方法，得到相应的元素。

++++++++

其实，你只要运行一下宏代码，设置断点逐步运行，然后慢慢观察各个变量的变化过程就行了。

cumulonimbus · 发表于 2011-7-7 23:37

群子小姐，你的意思是选8抽4的组合，第一位位置是int((k-1)/210)，第二位位置是int((k-1)/30)，第三位位置是int((k-1)/5)。接下去我就搞不明白了。
我这个人对算法比较笨。能否举一个实例作为说明。谢谢
为什么求余数就能转换为序数值呢？这一点没想明白。如果想通了这一点，一切都好理解了。能否劳烦再次解释一下否

[ 本帖最后由 cumulonimbus 于 2011-7-7 23:48 编辑 ]

Qinqinjiang · 发表于 2011-7-7 23:51

裙子老师好厉害~

Qinqinjiang · 发表于 2011-7-7 23:53

一个过程频繁调用工作表函数不知道速度是不是会慢点了

Application.WorksheetFunction

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

[分享] 求排列组合结果的自定义函数

评分