对任意数量的数组的所有可能组合求和并应用限制 [英] summing all possible combinations of an arbitrary number of arrays and applying limits

问题描述

我正在尝试生成一个任意数量的数组的所有组合的数组.从生成的数组中，我想添加一个约束，即数字的总和必须位于两个边界之间(例如下"和上")

I am trying to generate an array of all combinations of an arbitrary number of arrays. From the generated array, I would like to add an constraint that the sum of the numbers must lie between two bounds (say 'lower' and 'upper')

一种方法是使用

One method of doing this is to use cartersian, sum the elements, and select the ones that fall within the lower and upper bounds. However, the main limitation is that it is possible to run out of memory given a large number of input arrays. Another method is to use 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)]

此方法可提高内存效率，但是如果数组很大，则此方法可能会非常慢，例如此示例在十分钟的时间内运行:

This method is memory efficient, but can be very slow if the arrays are large, such as this example which runs in the 10's of minutes:

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

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

I'm looking for a faster method.

推荐答案

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

You could use recursion. For example, if item has been selected from the first array, then the new lower and upper limits for the rest of the arrays should be lower-item and upper-item.

这里的主要优点是，您可以在每个阶段短路元组的枚举.考虑所有值均为正的情况.那我们可以 自动抛出其他数组中大于任何值的值 upper-item.这样可以智能地缩小每个搜索空间的大小 递归级别.

The main advantage here is that you can short-circuit the enumeration of tuples at each stage. Consider the case when all the values are positive. Then we can automatically throw out any value in the other arrays that is bigger than upper-item. This intelligently reduces the size of the search space at each level of the recursion.

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_positive比arraysums快688倍:

---

For this test case, arraysums_recursive_all_positive is over 688x faster than arraysums:

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中的所有值均为正.我们还可以调整lower和upper限制以解决值的这种移动.因此，我们可以将所有正值都简化为arrays的特殊情况:

---

In the general case, when the values in arrays may be negative, then we can add an appropriate amount to each value in arrays to guarantee that all the values in the new arrays is positive. We can also adjust the lower and upper limits to account for this shifting of values. Thus we can reduce the general problem to the special case of arrays with all positive values:

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不:

Notice that arraysums_recursive handles negative values correctly, while arraysums_recursive_all_positive does not:

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_recursive比arraysums_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倍.

这篇关于对任意数量的数组的所有可能组合求和并应用限制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！