I am trying to make a powerset of a list for the first item of that list in ascending order. However, I couldn't find on StackOverflow how to tackle this specific problem.
When making a powerset of the following list:
backlog = [1, 2, 3, 4, 5]
with function:
def powerset(backlog):
s = backlog
return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))
gets me the following result:
[(), (1,), (2,), (3,), (4,), (5,), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5), (1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 4, 5), (1, 3, 4, 5), (2, 3, 4, 5), (1, 2, 3, 4, 5)]
However, I am looking for the powerset that includes the first item of the list backlog, in this case '1', in ascending order starting with [1] and ending with [1,2,3,4,5]. How can I only filter the subsets which contain '1'?
You could filter the powerset leaving only the elements that you care about (their 1st element is the 1st element of the starting list (backlog))
But (as I specified in the comment) this is kind of inefficient as it generates lots of values (half) just to later discard them.
So, an alternative would be to generate the powerset of the initial list without its 1st element, then prepend that element to every entry in the result.
code00.py:
#!/usr/bin/env python
import sys
import timeit
from itertools import chain, combinations
def powerset_orig(s):
combs = chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))
return (e for e in combs if e and e[0] == s[0])
def powerset(s):
if s:
tail1 = s[1:]
for e in chain.from_iterable(combinations(tail1, r) for r in range(len(tail1) + 1)):
yield (s[0],) + e
def main(*argv):
backlog = (1, 2, 3, 4, 5)
pso = list(powerset_orig(backlog))
print("Orig:", pso)
ps = list(powerset(backlog))
print("New: ", ps)
print("Equal:", pso == ps, " Length:", len(ps))
x = list(range(10000000))
count = 1000000
print("\nTime (orig):", timeit.timeit(lambda: powerset_orig(x), number=count))
print("Time (new):", timeit.timeit(lambda: powerset(x), number=count))
if __name__ == "__main__":
print("Python {:s} {:03d}bit on {:s}\n".format(" ".join(elem.strip() for elem in sys.version.split("\n")),
64 if sys.maxsize > 0x100000000 else 32, sys.platform))
rc = main(*sys.argv[1:])
print("\nDone.\n")
sys.exit(rc)
Output:
[cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q074376434]> "e:\Work\Dev\VEnvs\py_pc064_03.09_test0\Scripts\python.exe" ./code00.py Python 3.9.9 (tags/v3.9.9:ccb0e6a, Nov 15 2021, 18:08:50) [MSC v.1929 64 bit (AMD64)] 064bit on win32 Orig: [(1,), (1, 2), (1, 3), (1, 4), (1, 5), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 4, 5), (1, 3, 4, 5), (1, 2, 3, 4, 5)] New: [(1,), (1, 2), (1, 3), (1, 4), (1, 5), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 4, 5), (1, 3, 4, 5), (1, 2, 3, 4, 5)] Equal: True Length: 16 Time (orig): 1.1748076 Time (new): 0.2947546999999999 Done.
As seen, in this situation the latter variant performs ~4X better (time-wise).