5

I have difficulties using NumPy and/or Pandas for working with a 2D list to:

  1. Get the sum of unique combination of all elements without choosing from same row again (it should be 81 combinations for the array below).

  2. Print the row and column of the each element in the combination.

For example: 

arr = [[1, 2, 4], [10, 3, 8], [16, 12, 13], [14, 4, 20]]

(1,3,12,20), Sum = 36 and (row, col) =  [(0,0),(1,1),(2,1),(3,2)]

(4,10,16,20), Sum = 50 and (row, col) =[(0,2),(1,0),(2,0),(3,2)]
Neuron
  • 5,141
  • 5
  • 38
  • 59
vkb
  • 458
  • 1
  • 7
  • 18
  • I tried regular python `for` loops. But i need to use high performance data structures from numpy/panda. I searched lot of forums but couldnt find how to loop over all combinations of elements. – vkb Dec 11 '16 at 17:59

2 Answers2

5

Approach by creating all such combinations and summing : Here's a vectorized approach using itertools.product and array-indexing -

from itertools import product

a = np.asarray(arr)  # Convert to array for ease of use and indexing
m,n = a.shape
combs = np.array(list(product(range(n), repeat=m)))
out = a[np.arange(m)[:,None],combs.T].sum(0)

Sample run -

In [296]: arr = [[1, 2, 4], [10, 3, 8], [16, 12, 13], [14, 4, 20]]

In [297]: a = np.asarray(arr)
     ...: m,n = a.shape
     ...: combs = np.array(list(product(range(n), repeat=m)))
     ...: out = a[np.arange(m)[:,None],combs.T].sum(0)
     ...: 

In [298]: out
Out[298]: 
array([41, 31, 47, 37, 27, 43, 38, 28, 44, 34, 24, 40, 30, 20, 36, 31, 21,
       37, 39, 29, 45, 35, 25, 41, 36, 26, 42, 42, 32, 48, 38, 28, 44, 39,
       29, 45, 35, 25, 41, 31, 21, 37, 32, 22, 38, 40, 30, 46, 36, 26, 42,
       37, 27, 43, 44, 34, 50, 40, 30, 46, 41, 31, 47, 37, 27, 43, 33, 23,
       39, 34, 24, 40, 42, 32, 48, 38, 28, 44, 39, 29, 45])

Memory-efficient approach : Here's an approach without creating all those combinations and instead using on-the-fly broadcasted summations and the philosophy is very much inspired by this other post -

a = np.asarray(arr)
m,n = a.shape
out = a[0]
for i in range(1,m):
    out = out[...,None]  + a[i]
out.shape = out.size # Flatten
Community
  • 1
  • 1
Divakar
  • 218,885
  • 19
  • 262
  • 358
1

You can use product function from itertools:

from itertools import product    
y = [sum(p) for p in product(*arr)]

len(y)
# 81

An example with a smaller list:

arr = [[1,2],[3,4],[5,6]]
[sum(p) for p in product(*arr)]
# [9, 10, 10, 11, 10, 11, 11, 12]
Psidom
  • 209,562
  • 33
  • 339
  • 356
  • Thanks, it doesn't print the (row,col) index of elements that helped in arriving at that sum. How would i do it.? – vkb Dec 11 '16 at 18:05