hiyume hiyume - 1 year ago 54
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

Answer Source

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.