hiyume - 1 year ago 94
Python Question

# Lists: using better slicing to find iterative sums of subsets

Say I have a list,

``````A = range(1, 6) = [1, 2, 3, 4, 5]
``````

`B`
, the end result, is a list of lists. Given
`i`
and
`j`
, how would you make a list of iterative sums where index
`i`
bounds one side and
`j`
the other?

`B[j] = sum(A[j:i+1] or A[i:j+1])`
depending on whether
`j`
or
`i`
is larger.

Examples for indices 0 and 2:

``````B[0] = [1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5]
= [1, 3, 6, 10, 15]
B[2] = [1+2+3, 2+3, 3, 3+4, 3+4+5]
= [6, 5, 3, 7, 12]
``````

======

Current code (works) is two
`for`
loops, very brute force. I think there should be a way to use
`reduce`
?

``````A = range(1,6)
n = len(A)
B = []
for j in xrange(n):
b = []
for i in xrange(n):
if j <= i:
b.append(sum(A[j:i+1]))
else:
b.append(sum(A[i:j+1]))
B.append(b)

# print
for b in B:
print b
``````

Minor context: possibly part of my solution to project euler 82

You end up recalculating the sums many times. Instead create them once and look them up for each element of `b`:

``````A = range(1,6)
n = len(A)
mapping = {}
for i in xrange(n):
for j in xrange(i,n):
mapping[i,j] = sum(A[i:j+1])

B = []
for j in xrange(n):
b = []
for i in xrange(n):
if j <= i:
b.append(mapping[j,i])
else:
b.append(mapping[i,j])
B.append(b)
``````

you could eliminate the need to check `j<=i` if you just make the mapping work for both `[i,j]` or `[j,i]`:

``````mapping = {}
A = range(1,6)
n = len(A)
for i in xrange(n):
for j in xrange(i,n):
mapping[i,j] = sum(A[i:j+1])
mapping[j,i] = mapping[i,j] #for both ways

B = [[mapping[i,j] for i in xrange(n)] for j in xrange(n)]
``````

Although notice that this means that every `B[x][y]` will directly coordinate to `mapping[x,y]` so you may just want to use the mapping by itself.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download