Forum Discussion
Working with Binary numbers BASE(..., 2, 7) and bit operations BITXOR, BITAND
That looks impressive and not a method I think I ever could have foreseen! And I see what you mean about the repetition in the binary tree. The method of m_tarler in the previous link also looks elegant with acceptable performance which I suspect could be further improved with some minor alterations. I will need to set some time aside to look at all this in more detail...
PS. Just to clarify in my last post it looks like a closing parenthesis was omitted from the first formula and, in the screenshot, the cell beneath 'Residual' contains a spilled array formula: =MinSubset(seats, 122)
That thunk method looks pretty neat - I was impressed by the speed too. In previous attempts working with thunks I had experienced performance issues that were difficult to circumvent. Passing the thunk array as an array parameter to SCAN is clever and appears much more efficient than passing as a lambda parameter - within MAKEARRAY for example.
My first attempt to improve efficiency was to apply memoization which is a standard technique to avoid recomputing values within the recursion. I started looking at converting some online code examples to lambdas by building a table of thunks before realising that this was going to be similar to your method but probably less fast!
A follow-up thought was to generate all decimal combinations in a single row of Pascal's triangle iteratively,
=SORT(REDUCE(0,SEQUENCE(n),LAMBDA(a,_,VSTACK(a*{1,2},a*{1,2}+1))),{1,2})With n = 12 for example this returns 2^12=4096 rows, the first column is the number of combinations k and the second is the decimal representation of the combination. To return just the COMBIN(n,k) combinations we only need keep combinations less than k,
=LAMBDA(n, k,
LET(
combs, REDUCE(
0,
SEQUENCE(n),
LAMBDA(a, i,
SORT(
VSTACK(
DROP(a, IF(i > n - k, INT(COMBIN(i - 1, n - k)), 0)) * {1, 2},
DROP(a, IF(i > k, -INT(COMBIN(i - 1, k)), 0)) * {1, 2} + 1
),
{1, 2}
)
)
),
BASE(TAKE(combs, , -1), 2, n)
)
)I expected this might be faster than the thunk approach but in practice it fell short due to the repeated SORT operations so likely needs further refinements. I was also surprised that COMBIN returns non-integers in some cases (e.g. try removing 'INT' with n=12 and k=6)
I wish I knew for how long these workarounds are to be needed. I suspect the vast majority of spreadsheet users will never make the jump to the Excel formula as a functional programming language and the nested array problem only makes it more intimidating!
Towers of Hanoi. I am not sure which discussion it was attached to but it was posted by Patrick (I have a copy). I do not know why it has disappeared, though. The algorithm appears to build a table of moves that lead to the solution but without ever calculating the current state of the problem.
BTW I am planning to attend EuSpRIG Annual Conference | European Spreadsheet Risk Interest Group.
The programme looks quite varied this year.
Ok, so after several weeks of head banging, i feel like there may finally be some progress!
First, as far as i'm aware the list of scalable alternatives to the basic REDUCE/VSTACK method for stacking arrays now includes: nested reduce, recursive bisection, thunk arrays and lambda accumulators. Several examples are given in earlier comments; a relatively efficient implementation utilising lambda accumulators could be
BYROWλ =LAMBDA(array, function, LET( n, ROWS(array), k, CEILING.MATH(LOG(n,2)), REDUCE( LAMBDA(r,function(CHOOSEROWS(array,r))), SEQUENCE(k,,0), LAMBDA(a,i,LAMBDA(j,IF(j+2^i<=n,VSTACK(a(j),a(j+2^i)),a(j)))) )(1) ) )Second, for enumerating combinations, tests suggest lookups can be faster than stacking when returning longer result sets and that 2D-arrays may be needed to overcome decimal precision limitations such as:
=LAMBDA(n,k, REDUCE(SEQUENCE(n-k+1),SEQUENCE(k-1,,2),LAMBDA(a,j, LET(r,ROUND(COMBIN(SEQUENCE(n-k+1,,j),j),), i,SEQUENCE(@TAKE(r,-1,1)), HSTACK( CHOOSEROWS(a,i-XLOOKUP(i,r,VSTACK(0,DROP(r,-1)),,1)), XMATCH(i,r,1)+j-1 ) ) )))(20,10)P.S. was there a Towers of Hanoi lambda posted here previously? Maybe I was hallucinating but I had been hoping to check it out when it seemed to vanish!
