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!
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!
PeterBartholomew1 Ok now for my questions to Peter...
you have a line:SCAN(initialise, SEQUENCE(), NextCombinationλ(count,pick))
then in Next Combination you have:
= LAMBDA(n,p,
LAMBDA(initial,s,so does the (count,pick) of the lambda caller get assigned to the outer Lambda into n,p and then the SCAN variables get passed to the inner Lambda as initial, s ????
This is a very interesting structure to me that I haven't seen/played with.
If i understand correctly your 'place' and 'increment' variables are basically reconstructing the DECIMAL value? or is there something more?
I'm really perplexed my your Max lambda using MAX() as it appears those are (potentially) ascii characters at that point. did you try it when you exceed 9?
Thank you both, the exercise and diving into the solutions has been very educational.
Yes, you are correct that I used 'place' and 'increment' in lieu of DECIMAL. Sadly, I had not come across DECIMAL though I assume it was introduced at the same time as BASE! 😞
The function definition
NextCombinationλ = LAMBDA(n,p, LAMBDA(initial,s, LET( increment, 1 + DECIMAL(initial,n), converted, BASE(increment,n,p), vector, Explodeλ(converted), modified, SCAN( , vector, Maxλ), CONCAT(modified) ) ));now reads somewhat better. Your understanding of the parameter strings for 'NextCombinationλ' is also correct. It would be possible to take the process further and provide each of the parameters individually, expressing the function in its 'Curried' form. Such a form takes the parameters one at a time from left to right. The function is only evaluated when the final parameter value is provided. In this case, I wanted to provide 'n' and 'p' explicitly within a parameter string but allow the function to accept the remaining parameters from the Lambda helper function.
At the time I was developing the formula, I did not think going beyond 9 items was going to be a practicality, so I did not consider the possibility that 'A' and 'B' were going to appear as 'digits'! I guess redefining
Maxλ = LAMBDA(u, v, IF(u>v, u, v));would be a start. My search for 'readability' above all, has taken me down a path of long variable names, avoiding nested formulas, and placing each statement on a new line. I even asked for an option to use ':=' as an assignment operator in place of alternate comma separators.
The penalty is that my formulas are somewhat idiosyncratic and sometimes the natural language readability can mask the underlying syntax.
- ah thank you. it is good to know how the lambda callers nest that way.
Now i think our codes are essentially identical except i believe in your main lines 4-8 could be reduced to just:
indices, SCAN( ,SEQUENCE(....
as the 0000 value will be created by default (at least it appeared to work for me).
I was able to extend yours to 14 items, pick 9, 20,661,046,784 permutations. Excel wanted no part of 15 items!
I'd be interested in knowing the timing of the solutions vs. having a 'cheat sheet' of all the item positions (as constants) and simply looking up each element to obtain the item name.
Impressive! I'm still studying how you pulled this off. When I thought of this experiment several weeks ago, I began by studying the occurrences for each item in each column looking for patterns in the numbers.
This is the distribution of items in each column. There's some symmetry but probably not enough to go on that would top anything you've created. It's interesting that when UNIQUE is used on the above matrix, the occurrences for each number is 2 with the exception of 2 numbers appearing 4 times.
The key line is
modified, SCAN( , vector, Maxλ),which scans a row of indices to ensure each sequence increases monotonically. That allows the algorithm to make massive strides forward to the next possible combination rather than simply incrementing through the permutations and testing the outturn.
PeterBartholomew1 Patrick2788 Ok so I will submit mine but I think it is very similar to Peter's (but I have some questions for him...):
=LET(b, COUNTA(Items), combN, COMBINA(b,pick), n, SEQUENCE(combN,,0), series, SCAN(,n,LAMBDA(p,i, CONCAT(SCAN(0, MID(BASE(DECIMAL(p,b)+1,b,pick),SEQUENCE(pick),1),LAMBDA(pp,ii,IF(pp>ii,pp,ii)))))), INDEX(Items,DECIMAL(MID(series,SEQUENCE(1,pick),1),b)+1))Peter's is much more readable than mine but I still get lost. In mine I create a list of possible options using base() which is the same from what I can tell. I build my list by a manual sequential adding 1 and then make sure it isn't less then the index before it. In looking back it appears you guy originally did a filtering but I think this is how Peter's new version works also. My series is built on line 2 and proud to say this is the first time I found an advantage to doing a SCAN() without the initialize value to force it to use the first value in the sequence (zero in this case).
Since it is hard to read in the middle is BASE(DECIMAL()+1) which converts the text to a number, then +1 and back to the text. then outside that is a MID() to break it into characters and those characters are sent through the SCAN with the IF(>,,). I use the IF(>,,) instead of MAX because I don't bother converting back to decimal until the end so the IF can handle the ascii.
maybe peter can run the speed test on this and see how it compares.
