Forum Discussion
LAMBDA Halloween Challenge
Finally, I have a solution!
This time I used a Lambda function to add 1 to the previous index (stored in base n) but before returning the value, I scanned the digits and copied the larger digit across.
WorksheetFormula = LET( count, COUNTA(Items), initialise, REPT("0",pick), indices, VSTACK( initialise, SCAN(initialise, SEQUENCE(combinations-1), NextCombinationλ(count,pick)) ), INDEX(Items, 1 + Explodeλ(indices)) )where
NextCombinationλ = LAMBDA(n,p, LAMBDA(initial,s, LET( place, n^SEQUENCE(1,p,p-1,-1), increment, 1 + SUM(place * Explodeλ(initial)), converted, BASE(increment,n,p), vector, Explodeλ(converted), modified, SCAN( , vector, Maxλ), CONCAT(modified) ) ) );supported by
Explodeλ = LAMBDA(term, MID(term, SEQUENCE(1,pick), 1)); Maxλ = LAMBDA(u, v, Max(u,v));I have just performed the calculation for 8 picks taken for 9 items in 300ms. Ther are 12,870 combinations and the permutations would have been over 43M!
Patrick2788 You can try the following approach:
=LET(COMBINA_SETS, LAMBDA(x,n,LET(
NEXT_SET, LAMBDA(ME,x,m,n,i,IF(i=0,x,LET(s,SEQUENCE(,n),y,x+1,
idx, XMATCH(m,IF(i < n,IF(s>i,m+1,y),y),-1,-1),
ME(ME,IF(s=i,INDEX(y,idx),x),m,n,IF(idx=i,0,i-1))))),
y,TOCOL(x),m,ROWS(y),IF(AND(n=1,m=1),x, LET(cnts,
SEQUENCE(COMBINA(m,n)-1),idx,REDUCE(SEQUENCE(,n,1,0),cnts,LAMBDA(ac,i,
VSTACK(ac,NEXT_SET(NEXT_SET,IF(i=1,ac,TAKE(ac,-1)),m,n,n)))),
INDEX(y,idx))))),
COMBINA_SETS(B1:B6,D1))
It uses a user LAMBDA function COMBINA_SETS, which relays on a recursive user LAMBDA function NEXT_SET. To avoid creating a function in the Name Manager, I used the following trick: https://www.sumproduct.com/news/article/lambda-formulaic-recursion-its-all-about-me but you can remove the ME argument and define it in the Name Manager if you want (this a trick to use a recursive function inside of LET). I prefer this way because the sole purpose is to be used in COMBINA_SETS. If you enter a given set of values it returns the next one. The rest is just to use REDUCE to generate all the combinations based on NEXT_SET. It doesn't rely on Excel binary functions, since all of them have limitations on the number of digits of the binary number (DEC2BIN and BASE).
As per the shared link: The current operand stack limit in Excel is 1,024. This should be borne in mind together with calculation times, as the current recursion limit is set as 1,024 divided by (number of lambda parameters + 1)
Better to reduce the input argument list in NEXT_SET, so it can be formulated like this:
=LET(COMBINA_SETS, LAMBDA(x,n,LET(y,TOCOL(x), m,ROWS(y),
NEXT_SET, LAMBDA(ME,x,i,IF(i=0,x,LET(s,SEQUENCE(,n),y, x+1,
idx,XMATCH(m,IF(i<n,IF(s>i,m+1,y),y),-1,-1),
ME(ME,IF(s=i,INDEX(y,idx),x),IF(idx=i,0,i-1))))),
IF(AND(n=1,m=1),x,LET(cnts,SEQUENCE(COMBINA(m,n)-1),
idx,REDUCE(SEQUENCE(,n,1,0),cnts,LAMBDA(ac,i,
VSTACK(ac,NEXT_SET(NEXT_SET,IF(i=1,ac,TAKE(ac,-1)),n)))),
INDEX(y,idx))))),
COMBINA_SETS(B1:B6,D1))
so the limit would be 256 digits (max pick) in the worst-case scenario. Which is bigger than the BASE function limit of 53 digits.
For example, for the input data: {1,2,3,4,5,6} to find the combinations of three elements
1 1 1
1 1 2 <- NEXT_SET(NEXT_SET,A1:C1,6,3,3)
1 1 3 <- NEXT_SET(NEXT_SET,A2:C2,6,3,3)
1 1 4 <- NEXT_SET(NEXT_SET,A3:C3,6,3,3)
1 1 5 <- NEXT_SET(NEXT_SET,A4:C4,6,3,3)
1 1 6 <- NEXT_SET(NEXT_SET,A5:C5,6,3,3)
1 2 2 <- NEXT_SET(NEXT_SET,A6:C6,6,3,3)
...
6 6 6 <- NEXT_SET(NEXT_SET,A56:C56,6,3,3)
The algorithm goes backward, from right to left doing the corresponding increments, if the maximum value is reached, then it goes to the next digit recursively doing the same. It follows the same intuitive process a human will do to generate all combinations.
Here is the output:
Not showing the entire list on the screen.
This solution doesn't generate a set that then requires removing duplicates, etc. it generates exactly the combinations required. It considers also special cases such as m=n, where we don't need a recursion process. It also works in case the input array is column-wise instead of row-wise.