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: 1,763
Thanks: 19

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: 12,862
Thanks: 94

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 offline  
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: 12,862
Thanks: 94

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 offline  
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: 12,862
Thanks: 94

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 offline  
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  
February 2nd, 2011, 01:25 PM   #11
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 12,862
Thanks: 94

Re: Equal sum of a subset and remainder of a set

Quote:
Originally Posted by michelkeijzers
Why does it help that I know it can be 80 at most?
It changes the algorithms that I'd consider using on the problem. I wouldn't search for superincreasing subsequences, for example.
CRGreathouse is offline  
February 2nd, 2011, 03:35 PM   #12
Math Team
 
Joined: Apr 2010

Posts: 1,763
Thanks: 19

Re: Equal sum of a subset and remainder of a set

Quote:
Originally Posted by michelkeijzers
I'm a native dutch speaker.
O, ik ook
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?
Hoempa is offline  
February 2nd, 2011, 04:17 PM   #13
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 12,862
Thanks: 94

Re: Equal sum of a subset and remainder of a set

Quote:
Originally Posted by michelkeijzers
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).
Does that mean just 1..80, or are there further restrictions?
CRGreathouse is offline  
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((n-1)^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((n-1)^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 at-first simple problem.
michelkeijzers is offline  
February 3rd, 2011, 03:12 AM   #15
Math Team
 
Joined: Apr 2010

Posts: 1,763
Thanks: 19

Re: Equal sum of a subset and remainder of a set

Quote:
Originally Posted by Je
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 }

Code:
Ik heb deze in LaTeX weergegeven.

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 108-8=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.
Hoempa is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 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.