如何计算从1到N的一系列数字的所有可能组合的数量？

Question

除此之外:

from itertools import combinations
def brute_force(x):
    for l in range (1,len(x)+1):
        for f in list(combinations(range(0,len(x)),l)):
            yield f
x = range(1,18)
len(list(brute_force(x)))

[OUT]:

131071

• 我怎样才能在数学上计算出所有可能组合的数量？

• 有没有办法在不计算可能的组合的情况下以计算方式进行计算？

Answer 1

始终存在2 ⁿ -1非空子集{1,...,n}.

例如,考虑清单['a','b','c']:

>>> [list(combinations(['a','b','c'],i)) for i in range(1,4)]
[[('a',), ('b',), ('c',)], [('a', 'b'), ('a', 'c'), ('b', 'c')], [('a', 'b', 'c')]]
>>> l=[list(combinations(['a','b','c'],i)) for i in range(1,4)]
>>> sum(map(len,l))
7

我们列表的长度是3,所以我们有2 ³ -1 = 7种组合.

对于range(10):

>>> l=[list(combinations(range(10),i)) for i in range(1,11)]
>>> sum(map(len,l))
1023      #2^10-1 = 1024-1=1023

请注意,如果要计算可以使用的空子集2^n.

实际上从数学的角度来看:

集合的k-组合是S的k个不同元素的子集.如果集合具有n个元素,则k-组合的数量等于二项式系数:

并适用于所有组合: