一组中所有子集的数量

Question

这就是我想出来计算长度为n,1,...,n的所有子集的长度为n的单个元素加倍的子集.很难描述......

def subsets(seq, *args):

    seqstart = [[seq[i] for i in args], ]

    if len(args) == 0:
        for i in range(len(seq)):
            seqstart += subsets(seq, i)
    elif len(args) < len(seq):
        for i in range(args[-1], len(seq)):
            seqstart += subsets(seq, *args + (i, ))

    return seqstart

例子:

>>> subsets(['x', 'y'])
[[], ['x'], ['x', 'x'], ['x', 'y'], ['y'], ['y', 'y']]

>>> subsets(['x', 'y', 'z'])
[[], ['x'], ['x', 'x'], ['x', 'x', 'x'], ['x', 'x', 'y'], ['x', 'x', 'z'], ['x', 'y'], ['x', 'y', 'y'], ['x', 'y', 'z'], ['x', 'z'], ['x', 'z', 'z'], ['y'], ['y', 'y'], ['y', 'y', 'y'], ['y', 'y', 'z'], ['y', 'z'], ['y', 'z', 'z'], ['z'], ['z', 'z'], ['z', 'z', 'z']]

根据序列的长度,子集(序列)的长度是多少？(我在50小时后杀死了这个过程,n = 14)

谢谢

迈克尔

编辑:谢谢大家.所以它是2n的二项式系数.

要获取所有子集而不是多个集合(所以总长度为2 ^ n)我需要替换

for i in range(args[-1], len(seq)):

同

for i in range(args[-1] + 1, len(seq)):

Answer 1

大小为n的多个集合的数量等于一组大小n的n等于二项式系数

/ 2n \
|    |
\ n  /

接下来,通过总结从0到n的k 重复的组合的数量.

对于n = 14,这产生40116600多个集合.