gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-01 00:15:01 25 4
gpt4 key购买 nike

我的问题:

例如,我有 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

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

最佳答案

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

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

关于python - 相同元素的排列 : efficiently avoid redundant permutations,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59394182/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com