Find distinct sub-array whose sum equal to a given number in python

Question

I have a following data frame in pandas

     order_id quant_bought
0       519            3
2       520            3
5       521            1
6       523            6
11      524            1
12      525            1
13      526            3
16      527            1
17      528            1
18      529            1
19      530            1
20      531            3
22      532            1
23      533            3
26      534            1
27      535            3

What I am trying to do is, find all the quant_bought values equals to sum 6. I have one variable which has dynamic value which, I get after some calculation.

required = 6

Now I am generating 6 dynamic list based on above variable value

required = []
for i in range(required):
   required.append([])

Above code will generate 6 dynamic lists.

Now I want to fill this list with all quant_bought elements which sums to 6

It should look like this.

required1 = [1,1,1,1,1,1]
required2 = [1,1,1,3]
required3 = [3,3]
required4 = [3,3]
required5 = [6]
required6 = [3]    ## Which is left out

And corresponding index so that I can subset on dataframe. I am doing following in python

## Sorting the dataframe in ascending order
tsp_data_unique_sorted = tsp_data_unique.sort(['quant_bought'], ascending=     
[True])


def tsum(currentSum,total,input,record,n):
   if total==sum :
      for i in range(0,n):
         if record[i]:
            print input[i]
        i = i+1
        for i in range(i,n):
            if record[i]:
                print input[i]
        print ""
        return

i = currentSum
for i in range(i,n):
    if total + input[i] > sum :
        continue
    if i > 0 and input[i] == input[i-1] and not record[i-1] : 
        continue
    record[i] = 1
    tsum(i + 1,total + input[i],input,record,l)
    record[i] = 0

record = []
sum = 6
input = tsp_data_unique_sorted['quant_bought'].values.tolist()
l = len(input)
for i in range(0,l):
   record.append(0)
print "From the array the elements equal to 6 are:"

Which gives me following output.

tsum(0,0,input,record,l)

1
1
1
1
1
1

1
1
1
3

3
3

6

But, it did not take 3 elements into consideration (3,3,3). I want to store these into dynamic list which I have created. Please help.

Tomer Levinboim · Answer 1 · 2016-01-11T19:49:28.573

2

You are describing the subset-sum problem which is known to be NP-complete. From the wiki entry:

"given a set of integers and an integer s, does any non-empty subset sum to s?"

For small instances of the problem (short lists, small target sum) a dynamic programming/recursion solution would be quick, but would scale very poorly beyond that.

Also, I'm not sure why in the title you wrote "Find UNIQUE .. " whereas in your provided example there is more than one sub-list that sums to 6.

edited Jan 11 '16 at 19:49

answered Jan 11 '16 at 19:10

Tomer Levinboim

992
12
18

The reason why I have mentioned Unique is because I want elements in the list to be used Exactly Once. I don't want to find all the subsets,element once used can't be used again because I need corresponding `order_id` to be tracked – Neil Jan 12 '16 at 02:04
I see what you mean. – Tomer Levinboim Jan 12 '16 at 02:40
How to do it? any idea – Neil Jan 12 '16 at 03:40
Here's an upvoted solution on stackexchange http://stackoverflow.com/questions/23087820/python-subset-sum. Others and more can be found by searching "subset sum python". They will all run very slowly for large arrays. – Tomer Levinboim Jan 12 '16 at 04:58
OK. But, I don't want to use list elements more than once. This is my condition and all the solutions I got on internet was using all possible subsets. – Neil Jan 12 '16 at 05:10
Actually, I don't understand.. Can you explain this sentences: "it did not take 3 elements into consideration (3,3,3)" ? what is (3,3,3) ? – Tomer Levinboim Jan 12 '16 at 07:30
(3,3,3) are the quant_bought values which it did not considered in the output. If you see there are 6 observations with value 3 – Neil Jan 12 '16 at 09:27
I still don't understand. (1) Why is (3,3,3) considered a solution? it does not sum to 6. (2) Can you give an example of an invalid solution that is proposed by the other algorithms? – Tomer Levinboim Jan 13 '16 at 07:49

Find distinct sub-array whose sum equal to a given number in python

1 Answers1