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!
Your solution is very efficient. Both of our approaches are similar in that goal is to create the 126x4 matrix (6 items, pick 4 in the example) of numbers.
I like how you don't generate much excess at all array-wise, so there's no need to FILTER. I'll need to brush up on BASE. Tip of the cap there!
Essentially, my approach is to generate an array of numbers from 1111 to 6666 (6 being the total number of items in the example).
=SEQUENCE(REPT(COUNTA(Items),pick)-REPT(1,pick)+1,,REPT(1,pick))Removed any numbers containing 0, 7, 8, and 9 because there's only 6 items and 0 is never selected.
=UNIQUE(BYROW(Arr,LAMBDA(row,IF(MAX(IFERROR(SEARCH(Exclude,row),0))=0,row,""))),,1)Converting scalar to array, sorting, joining, splitting, wrapping, etc.
=WRAPROWS(TEXTSPLIT(TEXTJOIN(",",,UNIQUE(BYROW(ExArray,LAMBDA(row,TEXTJOIN(",",,SORT(MID(row,SEQUENCE(,pick),1),,,1)))))),,","),pick)*1From there it was a matter of a lookup.
I'm going tinker with both solutions to see if I can get the combinations to exceed 3,003. There seems to be a limit with SEQUENCE that's preventing expanding the item and pick # beyond about 10 items or so.
By itself, this is as far as I can get SEQUENCE to calculate:
=SEQUENCE(1000000,53)I have had a further go at improving the efficiency of the calculation. However, the core idea is still to generate integers strings corresponding to the permutations and then filter out the repetitions. This time, rather than sorting and using UNIQUE, I have examined each number to check whether it is already correctly sorted left to right. That allows me to use FILTER. The limit I hit on calculation size is that the number of permutations must not exceed 2²⁰. I have attempted to use full array formulas rather than Lambda helper functions where possible. An example of that is in FilterDecrλ where I compare entire columns of the array rather than working row by row.
It must be possible to implement a counter that that replaces any rightmost 0s by the newly incremented digit to their left (creating a jump in the series) but the logic is likely to be more contorted.
Re: permutation limit
Yes, it seems 9 items, pick 6 (about 500,000 permutations) is a struggle to calculate. My solution calculates half the time while yours holds up a bit more than that. There were a few instances where Excel wouldn't update the elements in the array.It must be possible to implement a counter that that replaces any rightmost 0s by the newly incremented digit to their left (creating a jump in the series) but the logic is likely to be more contorted.
This seems to be the case. I've been messing around with some seldom used engineering functions like BITLSHIFT/BITRSHIFT but can only get so far with them. Even if I could get something to work there's the issue of using older functions that weren't intended to be used with arrays, so I believe there's some "lifting" being done - not optimal.