Re: Subsequence problem

On 2006-03-31, cmills28@xxxxxxxxx <cmills28@xxxxxxxxx> wrote:
I am trying to come up with a workable computer algorithm to solve the
following problem:

Given a sequence A of integers, find the first subsequence B that adds
up to a specified sum S. The original sequence A will be generated
randomly, where each element a[k] is between 0 and S.

I probably should accuse you of posting your homework assignment... But
I think it's quite easy. Here's a Python program, it probably has bugs
in:

from random import *

def sum(s):
if s == []: return 0
return reduce(lambda a, b : a + b, s)

def findB(A, S):
"""Return first subsequence B of A that adds up to S. Each element of A is
between 0 and S"""
i = j = 0

while 1:
B = A[i : j]
w = sum(B)

if w == S:
return B
elif w < S:
j += 1
elif w > S:
i += 1

# Each member of A is less than S, so this must be true
assert i <= len(A)

if j >= len(A):
return None

S = 100
A = [randint(0, S) for i in range(100)]

print A
print findB(A, S)
.