【高级通用】元素分组排列组合 的递归算法代码

香川群子

aoe1981 发表于 2014-11-10 14:53
比如：分组为3组，各组为3、4、5人，总人数为12人的组合总数是：3080种，至于排列数，从公式角度出发，这个 ...

1楼附件更新了，把每一个分组的组合计算过程在对应行标出，更加直观！

aoe1981

香川群子 发表于 2014-11-11 13:25
1楼附件更新了，把每一个分组的组合计算过程在对应行标出，更加直观！

我会再次细做关注的，我的正式版也已发布，我将那条道走到了底，原来没有“黑”，终于看到光明了……也希望您多检测下，别有什么不知道的错误！我也会抽空与您的新附件再行进行对比测试的！！！

aoe1981

香川群子 发表于 2014-11-11 13:25
1楼附件更新了，把每一个分组的组合计算过程在对应行标出，更加直观！

　　此时似乎更加和我发现的那个公式接近了……
　　

aoe1981

现在忽然发现一个问题：如果各组规模有相同的，有不同的，则结果中还是有重复的，也就是说需要进行再筛选，或者说这样的结果直接拿来就用或参考时，是没有意义的。比如：您1楼，5人分组为：2、2、1的排列当中，其实是有重复的：

AB|CD|E

CD|AB|E

各组间不重复组合，在各组规模都相同时有意义；
各组间不重复排列，在各组规模互不相同时有意义。


http://club.excelhome.net/forum.php?mod=redirect&goto=findpost&ptid=1164549&pid=7940412

aoe1981

　　我猜测：您的1楼的示例2，5人分组2、2、1的真正不重复分组可能应当是15种：
　　下面是我分三种组序（一共有3种组序：221、212、122）分别得到的：

221	A,B   C,D  E	8个
	A,B  C,E  D
	A,C  B,D  E
	A,C  B,E  D
	A,D  B,C  E
	A,D  B,E  C
	A,E  B,C  D
	A,E  B,D  C
212	A,B  C  D,E	4个
	A,C  B  D,E
	A,D  B  C,E
	A,E  B  C,D
122	A  B,C  D,E	3个
	A  B,D  C,E
	A  B,E  C,D

aoe1981

　　下面的研究过程证明我的猜测是正确的：

分组
A   C,B  E,D	A  E,D  C,B
A   D,B  E,C	A  E,C  D,B
A   D,C  E,B	A  E,B  D,C
B   C,A  E,D	B  E,D  C,A
B   D,A  E,C	B  E,C  D,A
B   D,C  E,A	B  E,A  D,C
C   B,A  E,D	C  E,D  B,A
C   D,A  E,B	C  E,B  D,A
C   D,B  E,A	C  E,A  D,B
D   B,A  E,C	D  E,C  B,A
D   C,A  E,B	D  E,B  C,A
D   C,B  E,A	D  E,A  C,B
E   B,A  D,C	E  D,C  B,A
E   C,A  D,B	E  D,B  C,A
E   C,B  D,A	E  D,A  C,B

附件如下：

香川与aoe附件结果对比.rar (105.7 KB, 下载次数: 39)

2014-11-11 21:31 上传

点击文件名下载附件

shine2012

厉害，经典帖子呀！！！

wcymiss

来个非递归的，返回的数字代表的是分配的组号：

1. Dim nCount As Long, arrData()
   
2. 
   
3. Sub cs()
   
4.     Dim t: t = Timer
   
5.     nCount = 0
   
6.     Const PersonCount = 10
   
7.     ReDim arrData(1 To 5000, 1 To PersonCount)
   
8.     Call MyCombin(PersonCount, 2, 2, 2, 2, 2)
   
9.     Cells.Clear
   
10.     Range("a1").Resize(1, PersonCount).FormulaArray = "=char(column(" & Range("a1").Resize(1, PersonCount).Address & ")+64)"
    
11.     Range("a2").Resize(nCount, PersonCount).Value = arrData
    
12.     Debug.Print nCount
    
13.     Debug.Print Timer - t
    
14. End Sub
    
15. 
    
16. Private Sub MyCombin(PersonCount As Integer, ParamArray Group())
    
17.     Dim i As Integer
    
18.     Dim j As Integer
    
19.     Dim arr() As Integer
    
20.     Dim NumCount() As Integer
    
21.    
    
22.     ReDim arr(1 To PersonCount)
    
23.     ReDim NumCount(1 To UBound(Group) + 1)
    
24.    
    
25.     i = 1
    
26.     Do
    
27.         Do: j = j + 1: Loop Until NumCount(j) < Group(j - 1)
    
28.         arr(i) = j
    
29.         NumCount(j) = NumCount(j) + 1
    
30.         j = 1
    
31.         For i = i + 1 To PersonCount
    
32.             Do Until NumCount(j) < Group(j - 1): j = j + 1: Loop
    
33.             arr(i) = j
    
34.             NumCount(j) = NumCount(j) + 1
    
35.         Next
    
36.         
    
37.         nCount = nCount + 1
    
38.         For i = 1 To PersonCount
    
39.             arrData(nCount, i) = arr(i)
    
40.         Next
    
41.         
    
42.         j = arr(PersonCount)
    
43.         NumCount(j) = NumCount(j) - 1
    
44.         i = PersonCount - 1
    
45.         Do While arr(i) >= arr(i + 1) Or NumCount(arr(i)) = 1
    
46.             If i = 2 Then Exit Sub
    
47.             NumCount(arr(i)) = NumCount(arr(i)) - 1
    
48.             i = i - 1
    
49.         Loop
    
50. 
    
51.         j = arr(i)
    
52.         NumCount(j) = NumCount(j) - 1
    
53.     Loop
    
54. End Sub
    

复制代码

香川群子

aoe1981 发表于 2014-11-11 20:56
　　我猜测：您的1楼的示例2，5人分组2、2、1的真正不重复分组可能应当是15种：
　　下面是我分三种组序（ ...

呵呵，只要按照1、2、2分组，并设置参数为：1,1,2即可得到不重复的15个结果：

A|BC|DE
A|BD|CE
A|BE|CD
B|AC|DE
B|AD|CE
B|AE|CD
C|AB|DE
C|AD|BE
C|AE|BD
D|AB|CE
D|AC|BE
D|AE|BC
E|AB|CD
E|AC|BD
E|AD|BC

参数值1、1、2的意思是：
第1组和第2组之间参数相同，为排列关系，即各种组合都需要体现。
而第2组和第3组之间参数相差1，为不重复组合关系。即 AB|CD 和 CD|AB 等价忽略。

…………这样就可以了。

wqfzqgk

强大，看看