Summing All Possible Combinations Of An Arbitrary Number Of Arrays And Applying Limits And Returning Indices

This is a modification of this question in which I would like to return the indices of the arrays elements in addition to the elements themselves. I've successfully modified arrays

Solution 1:

A key feature of arraysums_recursive is that it throws out values which can not possibly contribute to the result:

subarrays = [[item2 for item2 in arr if item2 <= upper-item] 
              for arr in arrays[1:]]

While throwing things out complicates the recording of indices, it's not too hard. First, in arraysums_recursive expand arrays to include the index as well as the item value:

defarraysums_recursive(arrays, lower, upper):
    arrays = [[(i, item) for i, item inenumerate(arr)] for arr in arrays]
    ...
    index, result = zip(*arraysums_recursive_all_positive(arrays, lower, upper))
    return result, index

Now rewrite arraysums_recursive_all_positive to handle arrays which consist of a list of lists of (index, item)tuples.

---

defarraysums_recursive(arrays, lower, upper):
    arrays = [[(i, item) for i, item inenumerate(arr)] for arr in arrays]
    minval = min(item for arr in arrays for i, item in arr)
    # Subtract minval from arrays to guarantee all the values are positive
    arrays = [[(i, item-minval) for i, item in arr] for arr in arrays]
    # Adjust the lower and upper bounds accordingly
    lower -= minval*len(arrays)
    upper -= minval*len(arrays)
    index, result = zip(*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, index

defarraysums_recursive_all_positive(arrays, lower, upper):
    # Assumes all values in arrays are positiveiflen(arrays) <= 1:
        result = [((i,), (item,)) for i, item in arrays[0] if lower <= item <= upper]
    else:
        result = []
        for i, item in arrays[0]:
            subarrays = [[(i, item2) for i, item2 in arr if item2 <= upper-item] 
                         for arr in arrays[1:]]
            ifmin(len(arr) for arr in subarrays) == 0:
                continue
            result.extend(
                [((i,)+i_tup, (item,)+item_tup) for i_tup, item_tup in 
                 arraysums_recursive_all_positive(subarrays, lower-item, upper-item)])
    return result

---

import numpy as np
N = 8
a = np.arange(N)
b = np.arange(N)-N/2    
result, index = arraysums_recursive((a,b),lower=5,upper=6)

yields result:

[(2.0, 3.0),
 (3.0, 2.0),
 (3.0, 3.0),
 (4.0, 1.0),
 (4.0, 2.0),
 (5.0, 0.0),
 (5.0, 1.0),
 (6.0, -1.0),
 (6.0, 0.0),
 (7.0, -2.0),
 (7.0, -1.0)]

and index:

((2, 7),
 (3, 6),
 (3, 7),
 (4, 5),
 (4, 6),
 (5, 4),
 (5, 5),
 (6, 3),
 (6, 4),
 (7, 2),
 (7, 3))