python - 相同元素的排列 : efficiently avoid redundant permutations

Question

这个问题已经有答案了:

permutations with unique values (20 个回答)

已关闭 3 年前。

我的问题:

例如，我有 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 个(大部分相同)排列？

<小时/>

遵循Lukas Thaler的建议和 Chris_Rands我已经检查了 sympy.utilities.iterables.multiset_permutations 的可能用途

In [1]: from itertools import permutations                                                

In [2]: from sympy.utilities.iterables import multiset, multiset_permutations             

In [3]: for n in (2,3): 
   ...:     l = [1]*n +[2]*n + [3]*n 
   ...:     ms = multiset(l) 
   ...:     print(n*3) 
   ...:     %timeit list(multiset_permutations(ms)) 
   ...:     %timeit set(permutations(l)) 
   ...:                                                                                   
6
568 µs ± 3.71 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
91.3 µs ± 571 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
9
9.32 ms ± 209 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
58.3 ms ± 323 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

在我看来

1. 对于可以忽略不计的计算量来说，无论如何都没关系
2. 当事情变得僵化时，Sympy 中的纯 Python 实现可以使用 set 轻松克服暴力方法。和itertools.permutations

因此我得出结论，我的问题与克里斯引用的问题重复，我投票结束它。

Answer 1

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

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))))