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 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
