Forum Discussion
Efficient approach to generate list of combinations with no repetition
- Apr 04, 2023
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)
)
- davidlealApr 04, 2023Iron Contributor
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 Advanced Formula Environment Add-ins, 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
- davidlealApr 04, 2023Iron Contributor
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.
- PeterBartholomew1Apr 04, 2023Silver Contributor
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?