集合的所有子集数量

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

一个集合的普通子集数量是2的N次方。

如果你想要长度为K的子集，并且允许重复，那么数量是N的K次方。可以把你的元素想象成某种数字系统里的数字。如果N是10，那么你的元素就是数字0到9。

如果你想要包含重复的子集的大小在1到N之间，那么总共有N的1次方加上N的2次方加上N的3次方，一直到N的N次方的集合。

Answer 2

对于一个包含N个元素的集合A，它的子集数量等于2的N次方。

Answer 3

一个大小为 n 的集合中，最多可以有 n 个元素的多重集合的数量，等于一个叫做二项式系数的数学概念。

/ 2n \
|    |
\ n  /

这个结果是通过把从 0 到 n 的组合数（可以重复选择的组合）加起来得到的。

比如，当 n=14 时，这样可以得到 40116600 个多重集合。