本帖最后由 看见星光 于 2021-11-26 09:55 编辑
不重复排列组合的问题是指从给定个数的元素集中取出指定个数的元素进行排列,同时要求取出的元素不重复。在日常工作中,常用于凑数、排班、不重复组合抽样等等。
举个例子。
如上图所示,假设A列有5个人名,现在需要从中抽取4个不重复的人去搬砖,请问一共有多少种组合?并在D:G列计算出明细。
给大家分享几种常用解法,包含了函数、PQ、VBA和Python等。
PowerQuery解:- let//by看见星光
- 源 =Table.ToColumns(Excel.CurrentWorkbook(){[Name="表1"]}[Content]){0},
- m=4,y=List.Count(源)-1,//m是需要抽取的个数
- fx=(x,n,lst)=>//索引,数量,结果
- if n=m then {lst} else List.Accumulate({x..y-(m-n)+1},{},(s,d)=>s & @fx(d+1,n+1,lst & {源{d}})),
- 结果=Table.FromRows(fx(0,0,{}))
- in
- 结果
复制代码
函数解:- =INDEX($A:$A,SMALL(MID(BASE(LARGE(IF(LEN(SUBSTITUTE(BASE(ROW($1:$31),2,5),"0",))=4,ROW($1:$31)),ROW(A1)),2,5),ROW($1:$5),1)*ROW($2:$6),COLUMN(B1)))
复制代码
VBA解:
对于Excel来说,解决这类问题使用频次最高、效率最高的还是VBA。提供三种参考解法,辅助数组解、二进制解和递归解。
1)递归回溯:
- Dim aData, aRes, m&, n&, k&
- Sub cb() '递归
- aData = Range("a2:a" & Cells(Rows.Count, 1).End(xlUp).Row)
- k = 0: m = UBound(aData): n = 4 '一共几个元素和取几个元素
- ReDim aRes(1 To Application.Combin(m, n), 1 To n)
- Call fx(1, 0, "")
- Range("d2").Resize(k, UBound(aRes, 2)) = aRes
- MsgBox "ok"
- End Sub
- Function fx(x, y, s) '索引,组合个数,组合结果
- Dim i&, j&, t
- If y = n Then '如果组合项个数等于目标
- k = k + 1: j = 0
- For Each t In Split(Mid(s, 2), ",") '取结果
- j = j + 1
- aRes(k, j) = t
- Next
- Exit Function
- End If
- For i = x To m - (n - y) + 1 '剪枝
- Call fx(i + 1, y + 1, s & "," & aData(i, 1)) '回溯
- Next
- End Function
复制代码
2)二进制:
- Sub cbb() '二进制
- Dim aData, aRes, i&, j&, k&, m&, y&, g&, s$, t$, n&
- aData = Range("a2:a" & Cells(Rows.Count, 1).End(xlUp).Row)
- m = 4: y = UBound(aData)
- ReDim aRes(1 To Application.Combin(UBound(aData), m), 1 To m) '目标组合结果的个数
- g = Evaluate("sum(combin(" & y & ",row(1:" & y & ")))") '所有组合的个数
- For i = 1 To g
- s = Application.Base(i, 2, y) '转二进制
- t = Replace(s, "0", "")
- If Len(t) = m Then '如果组合项个数等于目标
- k = k + 1 '计数器
- n = 0
- For j = 1 To y '遍历二进制字符
- If Mid(s, j, 1) = "1" Then
- n = n + 1
- aRes(k, n) = aData(j, 1)
- End If
- Next
- End If
- Next
- Range("d2").Resize(k, UBound(aRes, 2)) = aRes
- MsgBox "ok"
- End Sub
复制代码
3)辅助数组:
- Sub cbr() '辅助数组
- Dim aData, aRes, aRef, i&, m&, j&, k&, r, x&, n&
- aData = Range("a2:a" & Cells(Rows.Count, 1).End(xlUp).Row)
- m = 4 '取几个
- ReDim aRes(1 To Application.Combin(UBound(aData), m), 1 To m) '组合结果的个数
- ReDim aRef(0 To Application.Combina(5, 4), 1 To 2) '辅助数组
- For i = 1 To UBound(aData) '遍历数据源
- For j = 0 To k '通过辅助数组进行组合
- k = k + 1
- aRef(k, 1) = aRef(j, 1) & "," & aData(i, 1) '组合
- aRef(k, 2) = aRef(j, 2) + 1 '项数
- If aRef(k, 2) = m Then '如果组合项有m个
- n = n + 1
- r = Split(aRef(k, 1), ",") '取出装入结果数组
- For x = 1 To m
- aRes(n, x) = r(x)
- Next
- End If
- Next
- Next
- Range("d2").Resize(n, UBound(aRes, 2)) = aRes
- MsgBox "ok"
- End Sub
复制代码
Python解
最后说一下Python解。
最近总有朋友来询问学Python还是VBA?我的观点是:如果你是从事数据分析或者有意转岗数据分析的话,Python必会;如果你不是做数据分析的,只是正经的办公人员,日常处理的数据范畴并没有超过Office,那就选择VBA——Python学了仨月,用不上的话,俩周你就忘光了。
我倒不是说Python不强,它比VBA强多了。但这就好比你出门去马路对面的商店买东西,500米的距离,你是选择走路呢?还是开汽车呢?走路就是VBA,汽车就是Python,就这么回事。
VBA的解法思路Python都可以实现,比如递归:- def combine(r: list, k: int) :
- res=[] #最终结果
- path=[] #条件结果
- def backtrack(n, startIndex):
- if len(path) == k:
- res.append(path[:])#深度copy
- return #出口
- for i in range(startIndex,n-(k-len(path))+1):
- path.append(r[i]) #处理节点
- backtrack(n,i+1) #递归
- path.pop() #回溯并撤销处理过的节点
- backtrack(len(r),0)
- return res
- combine (['看见星光','公众号Excel星球','excel','ppt','word'],4)
复制代码
除此之外,Python还可以调库:
- from itertools import combinations
- name=['看见星光','公众号Excel星球','excel','ppt','word']
- res=[s for s in combinations(name,4)]
复制代码
……
案例文件下载:
4001-M选N的组合.rar
(391.96 KB, 下载次数: 114)
|