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) )
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)
)
PeterBartholomew1 thanks great solution too! I adapted it to be able to return not just 0,1 values, but the actual values of the x-array. I combined it with COMBIN.SETE I provided in the UPDATE section of my question as follows:
COMBIN.SETPB = LAMBDA(x, m, LET(
y, TOROW(x),
n, COLUMNS(y),
k, 2 ^ SEQUENCE(1, n, 0),
h, SEQUENCE(2 ^ n),
p, SIGN(BITAND(h, k)),
f, BYROW(p, LAMBDA(p, SUM(p))) = m,
z, IF(FILTER(p, f), y, NA()),
WRAPROWS(TOCOL(z, 2), m)))
since it has been proven the most efficient way so far to convert 0,1 values to x-array.
Note: I guess you are using https://www.microsoft.com/en-us/garage/profiles/advanced-formula-environment-a-microsoft-garage-project/, defining the formula via the Names tab, I converted it to a LAMBDA function, so it can be defined in the Module tab.
I tested for n=19, m=10, for the input array set:
SEQUENCE(,B1,10,10)
I run it several times and in all cases > 4secs. I defined the following performance function:
PERFORMANCE.SETPB = LAMBDA(x, y, LET(start, NOW(), out, COMBIN.SETPB(x, y),
IFERROR(HSTACK((NOW() - start) * 24 * 3600, out), ""))
)
and calling it as follows:
=PERFORMANCE.SETPB(SEQUENCE(,B1,10,10),B2)
maybe you have in mind a more efficient way to do the mapping from 0,1 values to x-array values, so we can improve your approach.
Note: Since it is based on a binary function BITAND which has a limit, the maximum number to represent is (2^48)-1, therefore m <= 48.
Thanks
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.
@Peter Bartholomew another comment BYROW is less efficient than MMULT per my performance testing. I modified your approach as follows:
COMBIN.SETPB_A = LAMBDA(x, m, LET( y, TOROW(x), n, COLUMNS(y), k, 2 ^ SEQUENCE(1, n, 0), h, SEQUENCE(2 ^ n), p, SIGN(BITAND(h, k)), f, MMULT(p, SEQUENCE(n, , 1, 0)) = m, z, IF(FILTER(p, f), y, NA()), WRAPROWS(TOCOL(z, 2), m) ) )When I tested it under Excel Web, now it provides the best performance overall, considering the limitation mentioned before about the limit of m <= 48 due to the binary function limitation, but the truth is that any solution will crash before reaching that number at least with the current computing excel capacity.
I used SEQUENCE(n,,1,0) over SEQUENCE(n)^0 because I tested them separately and the first one seem to be a little bit faster.