
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: 1,762 Thanks: 14  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: 12,859 Thanks: 94  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: 12,859 Thanks: 94  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: 12,859 Thanks: 94  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). 
February 2nd, 2011, 01:25 PM  #11  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,859 Thanks: 94  Re: Equal sum of a subset and remainder of a set Quote:
 
February 2nd, 2011, 03:35 PM  #12  
Math Team Joined: Apr 2010 Posts: 1,762 Thanks: 14  Re: Equal sum of a subset and remainder of a set Quote:
Je voorstel om alle elementen met 4 te vermenigvuldigen klinkt goed. Het voordeel van een voorgedefinieerde set zie ik niet zo snel; kijk bijvoorbeeld naar deze set: {1, 5, 7, 8, 10, 11, 12, 26} De som is even 80, dus de som van 1 subset wordt 80/2=40. 26 is de grooste, daar moet 14 bij. 12 werkt niet, want je krijgt geen 2 meer. 11 werkt niet want je krijgt geen 3 meer. (eventueel: minimaal 12+11=23 komt nu al in de andere set. Dat is minder dan 40, dus we kunnen door) 10 werkt niet, want je krijgt geen 4 meer. (eventueel: minimaal 12+11+10=33 komt nu al in de andere set, dat is minder dan 40, dus we kunnen door) 8 werkt wel, want je krijgt nog 6. (Had 8 niet gekund, dan was in de andere set minimaal 41, dus was er geen oplossing) Dus: {26, 8, 5, 1} en {12, 11, 10, 7} zijn de subsets Voeg nu {14, 4} toe aan de set. Dan wordt de som (80+1/2=49 Volgens mij moet je dan weer opnieuw beginnen, of had je een methode om met de voorgedefinieerde set de nieuwe subsets ( (bijvoorbeeld; er zijn meerdere oplossingen.) {26, 14, 8, 1} en {12, 11, 10, 7, 5, 4}) te vinden? Misschien helpen de stappen om het probleem in kleinere stukjes te verdelen. Helpt dit een beetje? Shortly translated: I don't see the advantage of using a predefined set yet. Consider the set: {1, 5, 7, 8, 10, 11, 12, 26} Gives subsets: {26, 8, 5, 1} and {12, 11, 10, 7} "Add" to the set: {14, 4} Yields: {1, 4, 5, 7, 8, 10, 11, 12, 14, 26} With the subsets: (For example; there are multiple solutions) {26, 14, 8, 1} en {12, 11, 10, 7, 5, 4} How do the previous subsets contribute to finding the "new" subsets?  
February 2nd, 2011, 04:17 PM  #13  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,859 Thanks: 94  Re: Equal sum of a subset and remainder of a set Quote:
 
February 3rd, 2011, 01:25 AM  #14 
Joined: Jan 2011 Posts: 12 Thanks: 0  Re: Equal sum of a subset and remainder of a set
Thanks again for all help. I think it's best if I first take some time to experiment a little before asking a lot of advice. That probably means my first algorithm will be a bit far from optical but then I have at least some knowledge about the need for increase (tough as I already know it is NP complete, it probably can use every optimalization). I thought from a comment above that there could be a better algorithm if the values would be from a specified set, but probably this is not the case. Yesterday I changed the units of the values from kg to g, meaning that I have only integers which are all module 250. Of course I could temporary divide them all by 250 (or multiplying with 4 considering the original kg unit). This means the restrictions of set P are:  (Foreach v: v in P: 250 <= v <= 20000) (actually the following is even more restrictive: (Foreach v: v in P: v is_elem_of { 250, 500, 750, 1000, 1250, 1500, 2000, 2500, 3000, 4000, 5000, 7500, 10000, 12500, 15000, 20000 }) but this might not help  (Foreach v: v in P: v mod 250 = 0)  P contains probably of multiple instances of the same value (e.g. the value 500 probably is in the set multiple times). Probably this doesn't help either. Hoempa: dankje voor je uitleg. Ik ga vanavond of in het weekend proberen om je info in een algoritme te gieten, wat er waarschijnlijk op neerkomt dat ik een soort tree maak (dus elk element in de ene set of de andere plaats en controleer of het nog valide is. Zo ja, ga ik door tot het laatste element geplaatst is, zo niet dan stop ik die branch. Dan wordt het een O((n1)^2) algoritme (worst case). Short translation: Looks like I have to put the biggest element in a set, and for eevery other element (from high to low) put in either one, continues if it doesn't fail, otherwise stop. If the set is completely split and still valid, then it's ok. Btw, this O((n1)^2) algorithm need to be applied a lot of times, because I want to call this algorithm for almost every possible subset too. And this algorithm needs to be executed a lot of times too ... guess I need a supercomputer to solve a atfirst simple problem. 
February 3rd, 2011, 03:12 AM  #15  
Math Team Joined: Apr 2010 Posts: 1,762 Thanks: 14  Re: Equal sum of a subset and remainder of a set Quote:
Code: Zelf deel ik ze door 250, dat is niet persé nodig. Ik ben geen programmeur, maar misschien kan dit helpen; Omdat het aantal waarden voor elementen eindig is, kan je een lijst maken, waarin je mogelijke sommen uitschrijft. 2=1+1 3=2+1 4=3+1=2+2 5=4+1=3+2 6=5+1=4+2=3+3 8=6+2=5+3=4+4 10=8+2=6+4=5+5 12=10+2=8+4=6+6 16=12+4=10+6=8+8 20=16+4=12+8=10+10 30=20+10 40=30+10=20+20 50=40+10=30+20 60=50+10=40+20=30+30 80=60+20=50+30=40+40 Ik heb elk getal in hoogstens 2 termen uitgedrukt; als die 2 termen niet voorkomen, dan staan 1 of beide termen in de andere lijst. Volgens mij wordt dat een lang algoritme. Voorbeeld: {1,1,2,4,5,5,8,10,20,30,50,80} de som is 216, dus de som van een subset is 216/2=108 De eenheid 8 komt van de cijfers onder de 10. Die som is 26. De som in de subset is 8 respectievelijk 18. dus In subset 1, moet nog 1088=100 bijkomen. 80+20=100. dus subset 2 is Hier heb ik eigenlijk 1 set geconstrueerd en in de andere de overige elementen geplaatst. Short translation: You may consider the use of a list in your program. The idea is that you construct the set by using the needed sum of every subset, instead of puzzling arround. This way, it would be more of searching for the solution, rather than calculating the options. I'm not sure about the efficiency. Perhaps, you could construct all possibilities to expres the sum of a subset as a sum. e.g. 106=80+26=80+20+6... until you have terms that can be an element of your set. The restriction on the possible values of the elements seem useful, by looking at the last digit of the sums.  

Tags 
equal, remainder, set, subset, sum 
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 