How do I get a power set in a specific order?

Question

there some solutions for calculating a power set, but these I found on google doesn't give the power set in the order, which I need it. For example, if I want the power set of (1,2,3,4) common algorithms provide me with a power set in the following order:

()
(1)
(2)
(1 2)
(3)
(1 3)
(2 3)
(1 2 3)
(4)
(1 4)
(2 4)
(1 2 4)
(3 4)
(1 3 4)
(2 3 4)
(1 2 3 4)

But what I need is the following order:

()
(1)
(2)
(3)
(4)
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)
(1,2,3,4)

Because the number of elements can be quite high, it is not possible to calculate the whole power set and order it afterwards.

Has anyone some idea?

Answer 1

You want the combinations in order by length. In Python you can write:

import itertools

def subsets(iterable):
    "Generate the subsets of elements in the iterable, in order by length."
    items = list(iterable)
    for k in xrange(len(items) + 1):
        for subset in itertools.combinations(items, k):
            yield subset

>>> list(subsets([1,2,3,4]))
[(), (1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4),
 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)]

See this answer for an overview of algorithms that generate combinations. (Or you can look at Raymond Hettinger's Python implementation, itertoolsmodule.c lines 2026f.)