Forum Discussion
Efficient approach to generate list of combinations with no repetition
Forgive me for asking, but have I got the wrong end of the stick here?
= IF(Combinationsλ(n,m), "●","-") Combinationsλ = LET( k, 2 ^ SEQUENCE(1, n, 0), h, SEQUENCE(2 ^ n), p, SIGN(BITAND(h, k)), f, BYROW(p, LAMBDA(p, SUM(p))) = m, FILTER(p, f) )
PeterBartholomew1to be fair, I tested it under the same conditions on an Excel desktop, and your solution takes less than 2secs. COMBIN.SETE around 2.2 secs. All previous tests I ran using the free version of Excel Web, I don't know why I am getting different results on each Excel version, maybe they have a different implementation of the underlying functions used, or I would need to do more stress tests. The thing is that for n=20, m=10 around 184K combinations, both solutions don't return the result after waiting several minutes.
I performed a speed test for the 184756 combinations returned by ²⁰C₁₂, having first removed the text conversion to leave {0,1}s. On a Surface, core i7 laptop I got 5667 ms and a wall time of 5-6 seconds, as one might expect?
- Thanks, Peter, which test did you perform? which formula?, per my understanding, the version I posted based on your solution using MMULT is the fastest one, so I am going to accept your initial solution.
The formula I timed was the BYROW version, without any substitution by text or symbols. The MMULT version is slightly faster at 5000 ms. for the ²⁰C₁₀ case. The combinations can't go beyond n=20 because the intermediate calculation exceeds the available row count. Broadcasting text puts the timings up a shade once more.
=LET( h, 2 ^ SEQUENCE(1, n, 0), k, SEQUENCE(2 ^ n), p, SIGN(BITAND(h, k)), e, SEQUENCE(n, 1, 1, 0), f, MMULT(p, e) = m, FILTER(p, f) )PeterBartholomew1 Thanks, that is why I initially liked the recursive approach SETA, but due to REDUCE/VSTACK it is not efficient, because it generates exactly the total number of combinations, there is no need to generate more rows and then to filter, which allows going to n>=20, but because of its performance, it is not convenient. I hope Microsoft in the future improves REDUCE/VSTACK performance, it is a very useful pattern, but it is time-consuming. I added a https://feedbackportal.microsoft.com/feedback/idea/d90548de-bdd3-ed11-a81b-000d3a7bb563 in case you would like to vote it up.
MMULT is suprisingly very efficient. I've seen the limit quoted as an output of 5,460 elements for Excel 2007 and earlier. The 365 limit appears to be much greater (or limited by available memory).
- The MMULT function returns #VALUE! if the output exceeds 5460 cells.
Description of the limitations for working with arrays in Excel - Office | Microsoft Learn
The most I've been able to output is 9 million elements:
=LET(n,3000,r,SEQUENCE(n),c,SEQUENCE(,n),MMULT(r,c))
