Python3:计算两个列表总和为100的所有排列的最有效方法是什么？

Question

想象一下,我们有一个股票清单:

stocks = ['AAPL','GOOGL','IBM']

具体的股票并不重要,重要的是我们在这个清单中有n个项目.

想象一下,我们还有一个权重列表,从0%到100%:

weights = list(range(101))

给定n = 3(或任何其他数字),我需要生成一个矩阵,其中每个可能的权重组合总和达到100%.例如

0%, 0%, 100%
1%, 0%, 99%
0%, 1%, 99%
etc...

是否有一些itertools的方法可以做到这一点？什么东西在numpy？最有效的方法是什么？

Answer 1

优化这种方法的方法不是找出更快的方式来生成排列,而是生成尽可能少的排列.

首先,如果你只想要按排序顺序的组合,你会怎么做？

您不需要生成0到100的所有可能组合,然后对其进行过滤.第一个数字a可以是0到100之间的b任何数字.第二个数字可以是0到(100-a)之间的任何值.第三个数字,c只能是100-ab.所以:

for a in range(0, 101):
    for b in range(0, 101-a):
        c = 100-a-b
        yield a, b, c

现在,我们只是生成2000倍的加速,而不是生成100*100*100组合来过滤它们.100*50*1+1100*50*1+1

但是,请记住,仍有X * (X/2)**N答案.因此,X * (X/2)**N及时计算它们而不是X**N最佳 - 但它仍然是指数时间.并且没有办法解决这个问题; 毕竟,你想要一个指数的结果.

你可以寻找方法让第一部分itertools.product与reduceor 结合起来更简洁accumulate,但我认为它最终会降低可读性,并且你希望能够扩展到任意任意N,并且还能获得所有排列而不仅仅是排序的.所以,在你这样做之前保持可理解,然后在完成之后寻找方法来浓缩它.

你显然需要经历N步骤.我认为使用递归比循环更容易理解.

当n为1时,唯一的组合是(x,).

否则,对于从0到x的每个值a,您可以将该值与总和为xa的n-1个数的所有组合一起使用.所以:

def sum_to_x(x, n):
    if n == 1:
        yield (x,)
        return
    for a in range(x+1):
        for result in sum_to_x(x-a, n-1):
            yield (a, *result)

现在你只需要添加排列,你就完成了:

def perm_sum_to_x(x, n):
    for combi in sum_to_x(x, n):
        yield from itertools.permutations(combi)

但是有一个问题:permutations置换位置,而不是值.所以,如果你有,比如说(100, 0, 0),那六个排列是(100, 0, 0),(100, 0, 0),(0, 100, 0),(0, 0, 100),(0, 100, 0),(0, 0, 100).

如果N非常小 - 就像在你的例子中那样,N = 3且X = 100-可以很好地生成每个组合的所有6个排列并过滤它们:

def perm_sum_to_x(x, n):
    for combi in sum_to_x(x, n):
        yield from set(itertools.permutations(combi))

......但如果N能够变大,我们也会在那里谈论很多浪费的工作.

这里有很多关于如何在没有重复值的情况下进行排列的好答案.例如,请参阅此问题.借用该答案的实现:

def perm_sum_to_x(x, n):
    for combi in sum_to_x(x, n):
        yield from unique_permutations(combi)

或者,如果我们可以拖入SymPy或more-itertools:

def perm_sum_to_x(x, n):
    for combi in sum_to_x(x, n):
        yield from sympy.multiset_permutations(combi)

def perm_sum_to_x(x, n):
    for combi in sum_to_x(x, n):
        yield from more_itertools.distinct_permutations(combi)