[Tutor] Hi Folks...Need help with a modified version of the Subset sum problem.

[Peter Otten]

spiff007 wrote:

> Hi there Tutor folks
> 
> I need your help with a modified version of the subset sum problem [
> http://en.wikipedia.org/wiki/Subset_sum_problem].
> 
> The problem i am facing is a bit hard to describe (as most complex problem
> always are :D ), so please bear with my longish articulation :)
> 
> Here it goes :
> 
> After scrubbing some input data, i have two lists 'minutes' (elements are
> positive integers) & 'names' (elements are strings). They are the exact
> same length and each element of one corresponds exactly with the
> respective element of the other.
> 
> The elements in the minutes list are not unique; a sample list is :
> minutes = [60, 45, 30, 45, 45, 5, 60, 45, 30, 30, 45, 60, 60, 45, 30, 30,
> 60, 30, 30 ]
> names = ['abc', 'ghi', 'jkl', 'def', 'zab', 'wux', ........... ]
> 
> Now i need to pick some elements from the 'minutes' list (i.e. a subset of
> minutes) which add up to a certain sum ('target_sum1').
> I have to then do some processing with the *respective elements from the
> 'names' list, corresponding to, the elements i just picked from the
> 'minutes' list which sum upto target_sum1.*
> 
> I now have to remove these elements i picked (which add up to
> 'target_sum1' ) from the 'minutes' list, and essentially do a second pass,
> picking some elements, which add up to a certain other sum
> ('target_sum2'). Again, *retrieve the elements from the 'names' list*,
> *corresponding to the elements i just
> picked which sum upto 'target_sum2'*,  & do some processing on them.  And
> so  on.
> 
> Picking a subset of numbers, which add up to a certain target sum, is a
> well-known problem[1] & i have found the following code for it [2] :
> 
> I also have the code on a github gist
> https://gist.github.com/anonymous/5620886
> 
> def subset_sum_recursive(numbers,target,partial):
>     s = sum(partial)
> 
>     #check if the partial sum is equals to target
>     if s == target:
>         print "sum(%s)=%s"%(partial,target)
>     if s >= target:
>         return # if we reach the number why bother to continue
> 
>     for i in range(len(numbers)):
>         n = numbers[i]
>         remaining = numbers[i+1:]
>         subset_sum_recursive(remaining,target,partial + [n])
> 
> def subset_sum(numbers,target):
>     #we need an intermediate function to start the recursion.
>     #the recursion starts with an empty list  as partial solution.
>     subset_sum_recursive(numbers,target,list())
> 
> if __name__ == "__main__":
>     minutes = [3,9,8,4,5,7,10]
>     target_sum = 15
>     subset_sum(minutes,target_sum)
> 
>     #Outputs:
>     #sum([3, 8, 4])=15
>     #sum([3, 5, 7])=15
>     #sum([8, 7])=15
>     #sum([5, 10])=15
> 
> 
> This above code returns the elements of the 'minutes' list(subset of the
> 'minutes' list)  which add up to 'target_sum'.
> 
> *I am stuck on this point : *
> *I am unable to determine the list indices, of the elements of 'minutes'
> which add upto 'target_sum1', so i can retrieve the corresponding elements
> from the 'names' list, & do my processing on them.*

I think the easiest approach is to combine the two lists into a single one

pairs = zip(names, minutes)

or, if you really need the indices

pairs = list(enumerate(minutes))

and invoke subset_sum() with these pairs instead of minutes alone.
Of course you have to modify the sum() call to unpack the pairs:

s = sum(value for index, value in partial)

> *I also need the list indices to remove the elements which add upto
> target_sum1, and then run a "second pass", to determine the elements which
> add upto 'target_sum2'.*
> 
> Any & all explanations/links/code
> snippets/thoughts/ideas/suggestions/feedback/comments/ of the Python tutor
> community would be greatly appreciated.
> 
> Thanks a ton,
> calvin
> spiff007 at gmail.com
> 
> 
> 
> References
> 
> 1. http://en.wikipedia.org/wiki/Subset_sum_problem
> 2. http://stackoverflow.com/a/4633515/559456