Construct powerset without complements

Question

Starting from this question I've built this code:

import itertools

n=4
nodes = set(range(0,n))
ss = set()
for i in range(1,n+1):
  ss = ss.union( set(itertools.combinations(range(0,n), i)))

ss2 = set()
for s in ss:
  cs = []
  for i in range(0,n):
    if not(i in s):
      cs.append(i)
  cs=tuple(cs)
  if not(s in ss2) and not(cs in ss2):
    ss2.add(s)    
ss = ss2    

The code construct all subsets of S={0,1,...,n-1} (i) without complements (example, for n=4, either (1,3) or (0,2) is contained, which one does not matter); (ii) without the empty set, but (iii) with S; the result is in ss. Is there a more compact way to do the job? I do not care if the result is a set/list of sets/lists/tuples. (The result contains 2**(n-1) elements)

Additional options:

1. favorite subset or complement that has less elements
2. output sorted by increasing size

Answer 1

When you exclude complements, you actually exclude half of the combinations. So you could imagine generating all combinations and then kick out the last half of them. There you must be sure not to kick out a combination together with its complement, but the way you have them ordered, that will not happen.

Further along this idea, you don't even need to generate combinations that have a size that is more than n/2. For even values of n, you would need to halve the list of combinations with size n/2.

Here is one way to achieve all that:

import itertools

n=4

half = n//2
# generate half of the combinations
ss = [list(itertools.combinations(range(0,n), i))
        for i in range(1, half+1)]
# if n is even, kick out half of the last list
if n % 2 == 0:
    ss[-1] = ss[-1][0:len(ss[-1])//2]
# flatten
ss = [y for x in ss for y in x]
print(ss)