justin justin - 28 days ago 7
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)],
[])

Answer

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