相同元素的置换：有效地避免冗余置换

Question

我的问题：

例如，我有4个数字

a, b, c, d = np.random.rand(4)

并且我需要所有可能的总和a + b - c，a + b -d，b + c - d，b + c -a等

我发现我可以这样进行

from itertools import permutations

p = np.array(list(set(permutations([1, 1, -1, 0])))).T
sums = np.random.rand(4) @ p

到目前为止，我已经解决了我的问题...伤害我的感觉的是使用permutations(…)，因为将n数字合并的排列数当然是n!，而由set操作的滤波器将有效置换的数量减少到百分之几。

我的问题：

是否有可能获得，例如

p = np.array(list(set(permutations([1]*5 + [-1]*4 + [0]*6)))).T

[不计算所有1,307,674,368,000（几乎相同）的排列？

Answer 1

使用combinations可以降低复杂度：

n = 4
num_positive = 2
indexes = set(range(n))
idx = np.array([(*plus, minus)
                for plus in itertools.combinations(indexes, num_positive)
                for minus in indexes-set(plus)])
nums = np.random.rand(n)[idx]
nums[:,num_positive] = -num[:,num_positive]
sums = num.sum(axis=1)

Answer 2

我们可以通过首先使用combinations来选择求和中使用的数字，然后再次使用它来选择正（和负）数字来做到这一点。

from itertools import combinations, chain
from random import random

def our_sums_of(nums, num_positive):
    return (2 * sum(positives) - sum(nums) 
            for positives in combinations(nums, num_positive))

nums = [random() for _ in range(15)]
num_positive = 5
num_negative = 4

list(chain.from_iterable(map(lambda c: our_sums_of(c, num_positive), 
                             combinations(nums, num_positive + num_negative))))