Forum Discussion
Working with Binary numbers BASE(..., 2, 7) and bit operations BITXOR, BITAND
Maybe we need an archive folder to store the definitive recommendations and methods thought to be of long-term value? I think a pseudo-random number generator would qualify.
m_tarlerYes, having a repeatable random function can come in handy, I've quite often divided by 2^32 to get a non-volatile RAND alternative
PeterBartholomew1 Indeed, another possible candidate might be a 'combinations' function,
=combinations({"a";"b";"c";"d"},2)
which would return {"a","b";"a","c";"b","c";"a","d";"b","d";"c","d"}. I had been thinking about this off and on for a while but like SergeiBaklan couldn't see any reasonable route. I revisited again in light of the bisection method you provided recently based on a recursion over an array version of,
COMBIN(n,k) = COMBIN(n-1,k-1) + COMBIN(n-1,k)
For example with the following lambda definition =combinations(sequence(20),10) returns COMBIN(20,10)*10=1847560 elements.
combinations
=LAMBDA(arr, k,
IF(
k <= ROWS(arr),
IF(
k = 1,
arr,
DROP(
VSTACK(
combinations(DROP(arr, -1), k),
EXPAND(combinations(DROP(arr, -1), k - 1), , k, @TAKE(arr, -1))
),
k = ROWS(arr)
)
)
)
)
That was quite an achievement! I am not sure that my mind is correctly wired for recursion. I did get there but it was far from easy.
I picked out one step in your recursive calculation and, at least, it explained why the manner in which the combinations are ordered is a little unusual.
The other thing I noticed was that various nested calculations are performed more than once. I suppose that goes for the recursive formula for the count of combinations as well
COMBIN(n,k) = COMBIN(n-1,k-1) + COMBIN(n-1,k) = COMBIN(n-2,k-2) + COMBIN(n-2,k-1) + COMBIN(n-2,k-1) + COMBIN(n-2,k)Something else that had me puzzled for a moment was the type conversion
@TAKE(arr, -1)used to pad the expanded array.
I finally managed to take a look at your file attachment today and I think the BITXOR approach works well when applied to the problem of finding the minimal subsets for smaller data sets like the one in question. A couple of related thoughts occurred to me while looking through the lambda definitions...
1. To generate the list of possible sums one might also try:
=REDUCE(0,seats,LAMBDA(a,n,VSTACK(a,a+n))which appears very efficient compared to MMULT [0.33s with seats=sequence(20)]. Within the LET definition, this modification returned equivalent results for me:
combinations, SEQUENCE(2^n,,0), totalSeats, REDUCE(0,seats,LAMBDA(a,n,TOCOL(a+{0,1}*n)))2. For generating the minimal subsets, I also tried recursion with a threshold condition. Binary trees appear pretty powerful and applicable to a wide range of problems - but as you suggest the main issue is trying to keep a clear head!
Thanks for the reply, I will study it.
Meanwhile, to place the ball back in your court, I have been working up an alternative approach to the generation of all combinations of m objects from n.
I loved the elegance bisection formula and the way sets were combined. What troubled me was the duplication that was appearing. In 'normal' family trees there are 4 second generation ancestors and 8 third generation; in this case the numbers are 3 and 4 respectively with ancestors in common on both branches of the tree. This implies that some calculations are performed multiple times.
What I tried instead was to SCAN one side of Pascal's triangle and use the thunked results to initialise reduction steps on the other diagonal. The dimensions of the scanned region are m x (n-m)
I think I started out converting the function calls to Craig Hatmaker 's 5g functions but I have yest to reach the end of that process! I was happy to put the effort into the main program segments but wondered how far to go down the functional decomposition. I remember Craig's Central Error Reporting for VBA the entire calling tree was documented and would be returnable to assist the developer whilst being suppressed for an end user with no access to the code.
Just to add I should have checked the archives before posting the above formula. Two good alternative methods that came up in search results were (not coincidentally by both aforementioned contributors)
Evidence that there are sufficient high quality examples available now to build general purpose libraries of lambdas.