gpt4 book ai didi

python - 对任意数量的数组的所有可能组合求和并应用限制

转载 作者:行者123 更新时间:2023-11-28 22:32:58 26 4
gpt4 key购买 nike

我正在尝试生成一个包含任意数量数组的所有组合的数组。从生成的数组中,我想添加一个约束,即数字的总和必须位于两个边界之间(比如“下限”和“上限”)

这样做的一种方法是使用 cartersian ,对元素求和,并选择落在下限和上限范围内的元素。然而,主要的限制是在输入数组数量很大的情况下可能会耗尽内存。另一种方法是使用 itertools.product:

import itertools
import numpy as np

def arraysums(arrays,lower,upper):
p = itertools.product(*arrays)
r = list()

for n in p:
s = sum(n)
if lower <= s <= upper:
r.append(n)

return r

N = 8
a = np.arange(N)
b = np.arange(N)-N/2

arraysums((a,b),lower=5,upper=6)

返回这样的结果:

[(2, 3),
(3, 2),
(3, 3),
(4, 1),
(4, 2),
(5, 0),
(5, 1),
(6, -1),
(6, 0),
(7, -2),
(7, -1)]

此方法内存效率高,但如果数组很大,则可能会非常慢,例如这个在 10 分钟内运行的示例:

a = np.arange(32.)
arraysums(6*(a,),lower=10,upper=20)

我正在寻找一种更快的方法。

最佳答案

你可以使用递归。例如,如果从第一个数组中选择了 item,则其余数组的新下限和上限应为 lower-itemupper -item.

这里的主要优点是您可以短路每个阶段的元组枚举。考虑所有值为正的情况。那么我们可以自动丢弃其他数组中大于的任何值上项。这智能地减少了每个搜索空间的大小递归的层次。

import itertools

def arraysums_recursive_all_positive(arrays, lower, upper):
# Assumes all values in arrays are positive
if len(arrays) <= 1:
result = [(item,) for item in arrays[0] if lower <= item <= upper]
else:
result = []
for item in arrays[0]:
subarrays = [[item2 for item2 in arr if item2 <= upper-item]
for arr in arrays[1:]]
if min(len(arr) for arr in subarrays) == 0:
continue
result.extend(
[(item,)+tup for tup in arraysums_recursive_all_positive(
subarrays, lower-item, upper-item)])
return result

def arraysums(arrays,lower,upper):
p = itertools.product(*arrays)
r = list()

for n in p:
s = sum(n)
if lower <= s <= upper:
r.append(n)

return r

a = list(range(32))

对于这个测试用例,arraysums_recursive_all_positivearraysums 快 688 倍以上:

In [227]: %time arraysums_recursive_all_positive(6*(a,),lower=10,upper=20)
CPU times: user 360 ms, sys: 8.01 ms, total: 368 ms
Wall time: 367 ms

In [73]: %time arraysums(6*(a,),lower=10,upper=20)
CPU times: user 4min 8s, sys: 0 ns, total: 4min 8s
Wall time: 4min 8s

一般情况下,当arrays中的值可能为负数时,那么我们可以对arrays中的每个值加上适当的数量,以保证arrays中的所有值新的 arrays 是正的。我们还可以调整 lowerupper 限制来解释这种值的变化。因此我们可以将一般问题简化为具有所有正值的 arrays 的特殊情况:

def arraysums_recursive(arrays, lower, upper):
minval = min(item for arr in arrays for item in arr)
# Subtract minval from arrays to guarantee all the values are positive
arrays = [[item-minval for item in arr] for arr in arrays]
# Adjust the lower and upper bounds accordingly
lower -= minval*len(arrays)
upper -= minval*len(arrays)
result = arraysums_recursive_all_positive(arrays, lower, upper)
# Readjust the result by adding back minval
result = [tuple([item+minval for item in tup]) for tup in result]
return result

请注意 arraysums_recursive 正确处理负值,而arraysums_recursive_all_positive 不会:

In [312]: arraysums_recursive([[10,30],[20,40],[-35,-40]],lower=10,upper=20)
Out[312]: [(10, 40, -35), (10, 40, -40), (30, 20, -35), (30, 20, -40)]

In [311]: arraysums_recursive_all_positive([[10,30],[20,40],[-35,-40]],lower=10,upper=20)
Out[311]: []

虽然 arraysums_recursivearraysums_recursive_all_positive 慢,

In [37]: %time arraysums_recursive(6*(a,),lower=10,upper=20)
CPU times: user 1.03 s, sys: 0 ns, total: 1.03 s
Wall time: 852 ms

它仍然比 arraysums 快 290 倍。

关于python - 对任意数量的数组的所有可能组合求和并应用限制,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40410766/

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