python-3.x - 构造无补的幂集

Question

从this question开始我已经构建了这段代码:

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)

附加选项:

1. 最喜欢的元素较少的子集或补集
2. 输出按大小递增排序

Answer 1

当你排除互补时，你实际上排除了一半的组合。所以你可以想象生成所有组合，然后踢出它们的后半部分。在那里你必须确保不要踢出一个组合及其补充，但你订购它们的方式不会发生这种情况。

根据这个想法，您甚至不需要生成大小超过 n/2 的组合。对于n 的偶数 值，您需要将大小为n/2 的组合列表减半。

这是实现所有这些的一种方法:

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)