justin - 1 year ago 61
Python Question

# 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

`arraysums()`
,
`arraysums_recursive()`
, but I'm struggling with
`arraysums_recursive_anyvals()`
. Here are the details:

I modified
`arraysums()`
:

``````def arraysums(arrays,lower,upper):
products = itertools.product(*arrays)
result = list()

indices = itertools.product(*[np.arange(len(arr)) for arr in arrays])
index = list()

for n,k in zip(products,indices):
s = sum(n)
if lower <= s <= upper:
result.append(n)
index.append(k)
return result,index
``````

It now returns the elements and the indices of the elements:

``````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)],
[(2, 7),
(3, 6),
(3, 7),
(4, 5),
(4, 6),
(5, 4),
(5, 5),
(6, 3),
(6, 4),
(7, 2),
(7, 3)])
``````

I also modified @unutbu's recursive solution which also returns the same result as
`arraysums()`
:

``````def arraysums_recursive(arrays, lower, upper):
if len(arrays) <= 1:
result = [(item,) for item in arrays[0] if lower <= item <= upper]
index = []   # this needs to be fixed
else:
result = []
index = []
for item in arrays[0]:
subarrays = [[item2 for item2 in arr if item2 <= upper-item]
for arr in arrays[1:]]
result.extend(
[(item,)+tup for tup in arraysums(
subarrays, lower-item, upper-item)[0]])
index.extend(
[(item,)+tup for tup in arraysums(
subarrays, lower-item, upper-item)[1]])

return result,index
``````

Finally, I modified
`arraysums_recursive_anyvals()`
, but I can't seem to understand why it does not return the indices:

``````def arraysums_recursive_anyvals(arrays, lower, upper):
if len(arrays) <= 1:
result = [(item,) for item in arrays[0] if lower <= item <= upper]
index = []   # this needs to be fixed
else:
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 = []
index = []
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(
subarrays, lower-item, upper-item)[0]])
index.extend(
[(item,)+tup for tup in arraysums_recursive(
subarrays, lower-item, upper-item)[1]])

# Readjust the result by adding back minval
result = [tuple([item+minval for item in tup]) for tup in result]
return result,index
``````

results:

``````arraysums_recursive_anyvals((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)],
[])
``````

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:]]
``````

But throwing things out complicates the recording of indices. Instead of carefully keeping track of the remaining indices after throwing things out, I think it would be easier to compute the indices at the very end:

``````def arraysums_recursive(arrays, lower, upper):
# Record which item maps to which indice
index_maps = [{item:i for i, item in enumerate(arr)} for arr in arrays]
...
result = arraysums_recursive_all_positive(arrays, lower, upper)
...
# Regurgitate the index associated with each item
index = [tuple([index_map[item] for item, index_map in zip(tup, index_maps)])
for tup in result]
return result, index
``````

``````def arraysums_recursive(arrays, lower, upper):
index_maps = [{item:i for i, item in enumerate(arr)} for arr in arrays]
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]
index = [tuple([index_map[item] for item, index_map in zip(tup, index_maps)])
for tup in result]
return result, index

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

``````N = 8
a = np.arange(N)
b = np.arange(N)-N/2
print(arraysums_recursive((a,b),lower=5,upper=6))
``````

yields

``````([(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)],
[(2, 7),
(3, 6),
(3, 7),
(4, 5),
(4, 6),
(5, 4),
(5, 5),
(6, 3),
(6, 4),
(7, 2),
(7, 3)])
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download