My Math Forum Equal sum of a subset and remainder of a set

 Applied Math Applied Math Forum

 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 non-mathematical notation).
February 1st, 2011, 04:51 AM   #3
Math Team

Joined: Apr 2010

Posts: 2,702
Thanks: 331

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:
 Originally Posted by You example 2: P = { 3, 1, 1, 1, 2, 5 }
If a set of just integers has a disjoint subsets with the same sum, the sum of the set has to be even.
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:
 Originally Posted by You example 3: P = { 1, 2, 2, 3, 3, 5}
1+2+2+3+3+5=16. The sum of a subset will be 16/2=8.
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.
$8+7=15>9=$
so 8 and 7 are not in the same set.
$8+3>11\ne 9$
so 8 and 3 are not in the same set.
$7+3=10>9=$
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: 15,758 Thanks: 844 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Equal sum of a subset and remainder of a set This problem (a special case of SUBSET-SUM) is NP-complete, so there are no known polynomial-time 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: 15,758
Thanks: 844

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Equal sum of a subset and remainder of a set

Quote:
 Originally Posted by michelkeijzers I.e. it's not just set { a0, ..., an } but more like { 2 times a0, 3 times a2, ... x times ay }
So you have a multiple of 2, a multiple of 3, a multiple of 4, and so on? Or you just know that they're all multiples of something? Or what?

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 'Pseudo-polynomial 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: 15,758
Thanks: 844

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Equal sum of a subset and remainder of a set

Quote:
 Originally Posted by michelkeijzers 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).
So we can multiply by 4 and get integers. The question is whether we know anything about those integers.

Knowing that they're at most 80 does help a bit.

Quote:
 Originally Posted by michelkeijzers I read something about knapsacks, and yes, it's a special form: the subset sum. And I think I could use 'Pseudo-polynomial 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've never liked the term "pseudo-polynomial" because it really means "exponential".

Quote:
 Originally Posted by michelkeijzers I assume it would help that the values could be predefined and are multiples ... but does it make it a different problem then?
It's the same problem with multiple values as without. Mathematicians would call the underlying data structure a multiset rather than a set, but other than terminology it's not different. I don't know what you mean by "predefined" here.

 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

,

,

,

### find the smallest number of 4 digits which when divided by 40,50 and 60 leaves a remainder of 5 in each case.

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post msgelyn Number Theory 12 January 29th, 2014 04:47 PM redgirl43 Applied Math 1 April 21st, 2013 06:20 AM Arnie45 Number Theory 3 September 22nd, 2012 06:51 AM honzik Applied Math 0 June 9th, 2009 10:38 AM Arnie45 Abstract Algebra 0 January 1st, 1970 12:00 AM

 Contact - Home - Top