hiyume hiyume - 5 months ago 12
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

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.

Comments