
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
January 31st, 2011, 02:10 AM  #1 
Joined: Jan 2011 Posts: 12 Thanks: 0  Equal sum of a subset and remainder of a set
I have the following problem: I want to check if there exists a subset of a set that has the same sum as the sum of the remaining values of a set. Example: Assume set { 1, 3, 2, 0.5, 0.5 } In this case there exist a set { 1, 2, 0,5 } that sums up to 3.5 where the remaining elements { 3, 0.5 } also sums up to 3.5. Formal: Assume set P b = (Exist Q: Q is subset of P : sum(Q) = sum(P  Q)) Question: how to calculate b? Of course it is possible to check every possibility but this will be computationally slow (exponential increase). Does somebody know an algorithm how to calculate b smarter? For those who are interested in the real world application: I have a set of discs for dumbbells and I want to know if a certain set can be put on a dumbbell bar in a balanced way. Kind regards, Michel 
January 31st, 2011, 05:51 AM  #2 
Joined: Jan 2011 Posts: 12 Thanks: 0  Re: Equal sum of a subset and remainder of a set
I have thought more about this problem and I think I know a solution, however, I can't proof (for myself) if it is correct. The strategy to calculate b is: 1 Sort the set P, if P = {} > b = true 2 Pick the highest number r from P, add it to set R, remove from P 3 Starting from high to low, add values until the sum = r, if sum > r gets too high during looping, skip a value. If sum < r at the end > b = false 4 remove all values that lead to sum and remove them from P 5 If 1 value remains > b = false, of no values remain: b = true, if >= 2 values remaing > goto 2 example: P = { 3, 1, 5, 1 } steps: 1: sort: P = { 1, 1, 3, 5} 2: r = 5, P = { 1, 1, 3} 3: 3 + 1 + 1 = 5 4: P = {} 5: b = true example 2: P = { 3, 1, 1, 1, 2, 5 } 1: sort: P = { 1, 1, 1, 2, 3, 5} 2: r = 5, P = { 1, 1, 1, 2, 3} 3: 2 + 3 = 5 4: P = {1, 1, 1} 5: goto step 2 2: r = 1 3: 1 = 1 4: P = { 1 } 5: b = false example 3: P = { 1, 2, 2, 3, 3, 5} 1: sort: P = { 1, 2, 2, 3, 3, 5} 2: r = 5, P = { 1, 2, 2, 3, 3} 3: 3 + (skipped 3 > 0) + 2 = 5 4: P = { 1, 2, 3} 5: goto step 2 2: r = 3, P = { 1, 2} 3: 1 + 2 = 3 4: P = {} 5: b = true I think this works, but maybe I missed something. Can anybody help me in this? Greetings, Michel (sorry for the nonmathematical notation). 
February 1st, 2011, 04:51 AM  #3  
Math Team Joined: Apr 2010 Posts: 2,031 Thanks: 132  Re: Equal sum of a subset and remainder of a set
Hello Michel, Are dutch/a native dutchspeaker? (Assumed by your nickname) Sorting them seems useful to me. I would first add all the numbers. Quote:
3+1+1+1+2+5=13. We only have integers. 13 is odd. So your subsets don't exist. Once you added them, you can determine, if possible (even sum of set) what the sum will be for the other sets. Quote:
5 is in a set, so we will start there. 5+...=8 3 on the dots. 3 is in the set. P(*)={5, 3} (a different name than the initial set) Consider these steps: Example 4. P = {3, 7, 8} 3+7+8=18=even If the subsets exist, sum of a subset = 18/2=9. 8 is in a subset. so 8 and 7 are not in the same set. so 8 and 3 are not in the same set. so 7 and 3 are not in the same set. Does it help?  
February 2nd, 2011, 07:07 AM  #4 
Joined: Jan 2011 Posts: 12 Thanks: 0  Re: Equal sum of a subset and remainder of a set
Hello Hoempa, Thanks for your help. And yes, I'm a native dutch speaker. Btw, I found out my algorithm is incorrect. Counter example: set of { 1, 3, 2, 2 } would results sorted in { 1, 2, 2, 3 } > 3 will be removed, 1 +2 will be on the other side. 2 remains which will say it would be unbalanced. However 3 + 1 = 2 + 2 which is balanced. Check if the sum is even helps a lot. In real, numbers can be .25 or .5 or .75 so if I multiply with 4 I will get integers. The next of your solution seems very good ... I need to have also the possibilities (set combinations that are even), so it seems I have to iterate through them (more than once). I will need to think about it how to do that. But by putting the biggest element already in one set and checking the others will probably be the fastest way. It seems worst case it is factorial (meaning that if I have 10 integers, it will take 10! iterations worst case). Also, this is only part of a bigger problem so I have to check if it will be computational possible in reasonable time. Thanks already for the help! Greetings Michel 
February 2nd, 2011, 08:51 AM  #5 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 13,831 Thanks: 360 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic  Re: Equal sum of a subset and remainder of a set
This problem (a special case of SUBSETSUM) is NPcomplete, so there are no known polynomialtime solutions. Depending on the characteristics of your data there may be a fast solution  for example if you know the sets will be small or in a restricted range.

February 2nd, 2011, 09:19 AM  #6 
Joined: Jan 2011 Posts: 12 Thanks: 0  Re: Equal sum of a subset and remainder of a set
Thanks for the name of the problem (subset sum) and the big O number. I will read the article tonight when I have more time, but a quick look showed that is what I'm looking for. The set will be small however, as a programmer I like a generic solution in both number of elements and range of values. However there is a restriction I could use: the set of values which are used is from a mostly small set. I.e. it's not just set { a0, ..., an } but more like { 2 times a0, 3 times a2, ... x times ay }. However, I'm not a mathematician, so it would make the algorithm probably more difficult. I will give the (realtime) computation time when I'm finished for my set (set of 22 values). Greetings Michel 
February 2nd, 2011, 09:49 AM  #7  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 13,831 Thanks: 360 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic  Re: Equal sum of a subset and remainder of a set Quote:
Of course if you knew they were multiples of the same thing (e.g., 2n, 3n, 4n, 5n, ..., kn) that would tell you a lot, but I imagine that's not the case.  
February 2nd, 2011, 10:42 AM  #8 
Joined: Jan 2011 Posts: 12 Thanks: 0  Re: Equal sum of a subset and remainder of a set
Well actually it are multiples of something, namely 0,25 (kg). Then of course the multiplication factor could be something like 80 at max. (which equals 80 x 0,25 kg = 20 kg). Even more precise, if it would help I could make the values even known beforehand (like 0.25, 0.5, 1, 1.5, 2, 2.5, 3, 4, 5, 7.5, 10, 15, 20). If it would help the algorithm I could make these 'predefined', but it would be nice if additional numbers could be added later to this list of possible values. Multiple of these values can occur in a set, actually this is more common than not, e.g. 2 times 0.5, 4 times 2.5, 1 time 5. I read something about knapsacks, and yes, it's a special form: the subset sum. And I think I could use 'Pseudopolynomial time dynamic programming solution' to be found in http://en.wikipedia.org/wiki/Subset_sum_problem. I have to read it again because it's not that simple. I assume it would help that the values could be predefined and are multiples ... but does it make it a different problem then? Greetings and thanks for all help, Michel 
February 2nd, 2011, 11:04 AM  #9  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 13,831 Thanks: 360 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic  Re: Equal sum of a subset and remainder of a set Quote:
Knowing that they're at most 80 does help a bit. Quote:
Quote:
 
February 2nd, 2011, 12:59 PM  #10 
Joined: Jan 2011 Posts: 12 Thanks: 0  Re: Equal sum of a subset and remainder of a set
Why does it help that I know it can be 80 at most? I already thought it would be exponential ... like 2 ^ n (minus some combinations that are very easily to be invalid) What I mean with predefined is that I know the possible values in the set beforehand ... or at least, I have a list of values that someone can select to be in the set (0, 1 or multiple times). And I don't know if it would make it a different (hopefully) easier problem ... I'm going to check if I can write an algorithm (and te remove the most simple invalid sets). 

Tags 
equal, remainder, set, subset, sum 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
remainder  msgelyn  Number Theory  12  January 29th, 2014 04:47 PM 
Subset of a Function g[a] subset g[b]  redgirl43  Applied Math  1  April 21st, 2013 06:20 AM 
What is the remainder  Arnie45  Number Theory  3  September 22nd, 2012 06:51 AM 
Equal transformation on nonequal sets  honzik  Applied Math  0  June 9th, 2009 10:38 AM 
What is the remainder  Arnie45  Abstract Algebra  0  January 1st, 1970 12:00 AM 