How to make a powerset in ascending order for the first item in a list?

Question

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'?

Answer 1

You could filter the powerset leaving only the elements that you care about (their 1^st element is the 1^st 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).