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 > spiff...@gmail.com > > > > References > > 1. http://en.wikipedia.org/wiki/Subset_sum_problem > 2. http://stackoverflow.com/a/4633515/559456 _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor