python 3 : What is the most efficient way to calculate all permutations of two lists summing to 100?

Question

假设我们有一份股票 list :

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-a-b。所以:

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

现在，不再生成 100*100*100组合将它们过滤到 100*50*1+1 ，我们只是生成 100*50*1+1 ，实现了 2000 倍的加速。

但是，请记住 X * (X/2)**N 周围仍然存在答案。所以，在 X * (X/2)**N 中计算它们时间而不是 X**N可能是最优的——但它仍然是指数时间。没有办法解决这个问题；毕竟，您想要指数级的结果。

您可以使用 itertools.product 寻找使第一部分更简洁的方法结合reduce或 accumulate ，但我认为它最终会变得不那么可读，并且您希望能够扩展到任意 N ，并获得所有排列而不仅仅是排序的排列。因此，在您执行此操作之前，请使其易于理解，然后在完成后寻找方法对其进行压缩。

---

您显然需要完成 N 个步骤。我认为递归比循环更容易理解。

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

否则，对于从 0 到 x 的每个值 a，您可以得到该值，以及总和为 x-a 的 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 可以变大，我们也在谈论那里也有很多浪费的工作。

关于如何在没有重复值的情况下进行排列，这里有很多很好的答案。参见 this question ， 例如。从那个答案中借用一个实现:

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)