如何计算从 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)))

[输出]:

我怎样才能数学计算出所有可能组合的数量？
有没有办法在不枚举可能的组合的情况下进行计算？

Answer 1

假设您有一个来自 [1, 10) 的列表，并且您想要选择 3 个项目

数学

>>> math.factorial(9) // (math.factorial(3) * math.factorial(6))
84

这是combinations

的定义

_____n!_____
 k!(n - k)!

所以作为一个通用函数

def num_combinations(n, k):
    return math.factorial(n) // (math.factorial(k), math.factorial(n-k))

蛮力

>>> len(list(itertools.combinations(range(1,10), 3)))
84

Answer 2

总有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。

其实从数学的角度来说：

a k-combination of a set is a subset of k distinct elements of S. If the set has n elements, the number of k-combinations is equal to the binomial coefficient :

所有组合：

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

How to calculate the number of all possible combinations for a range of numbers from 1 to N?

python

math

combinations

itertools