My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
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
michelkeijzers is offline  
 
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).
michelkeijzers is offline  
February 1st, 2011, 04:51 AM   #3
Math Team
 
Joined: Apr 2010

Posts: 2,188
Thanks: 183

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.

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?
Hoempa is offline  
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
michelkeijzers is offline  
February 2nd, 2011, 08:51 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 14,096
Thanks: 444

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 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.
CRGreathouse is online now  
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
michelkeijzers is offline  
February 2nd, 2011, 09:49 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 14,096
Thanks: 444

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic
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.
CRGreathouse is online now  
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
michelkeijzers is offline  
February 2nd, 2011, 11:04 AM   #9
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 14,096
Thanks: 444

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic
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.
CRGreathouse is online now  
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).
michelkeijzers is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2014 My Math Forum. All rights reserved.