python - 集合的所有子集的数量

Question

这是我用来计算长度为 n 的集合的所有长度为 0, 1, ... , 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']]

依赖于序列长度的子集(序列)的长度是多少？ (我在 n=14 的情况下在 50 小时后终止了进程)

谢谢

迈克尔

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

要获取所有子集而不是多重集(因此总长度为 2^n)，我需要替换

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

与

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

Answer 1

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

/ 2n \
|    |
\ n  /

接下来是对 number of combinations with repetition 的总结k 从 0 到 n。

对于 n=14，这会产生 40116600 个多重集。