Re: Divide array of integers into most similar value halves

Replies are listed 'Best First'.
Re^2: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 01, 2008 at 20:01 UTC
I read about it, but the Partition Problem just tells you if the list of numbers can be partitioned into 2 halves that have the same sum. I'm not really interested into checking that. I don't mind them having the same or different sum. I only want the best possible partition. Thanks anyway.	[reply]
Re^3: Divide array of integers into most similar value halves by Skeeve (Parson) on Sep 01, 2008 at 20:05 UTC
Strange! The german wikipedia page states "Gesucht wird eine Aufteilung dieser Zahlen auf zwei Haufen, so dass die Differenz der Summen der Zahlen in den beiden Haufen möglichst klein ist." (Find a partition such that the diffference of the sum of each heap is minimal). And this is exactly what you're after. `s$$([},&%#}/&/]+}%&{});#$&&s&&$^X.($'^"%]=\&(\|?{%` `+`.+=%;.#_}\&"^"-+%*).}%:##%}={~=~:.")&e&&s""`$''`"e	[reply] [d/l] [select]
Re^4: Divide array of integers into most similar value halves by Pepe (Sexton) on Sep 01, 2008 at 20:13 UTC
I guess I'll be totally fine with that if the German definition is true and there is a way of implementing that in perl. Any ideas on how to do it? I can't read German.	[reply]
Re^5: Divide array of integers into most similar value halves by Skeeve (Parson) on Sep 02, 2008 at 04:21 UTC
Re^3: Divide array of integers into most similar value halves by JadeNB (Chaplain) on Sep 01, 2008 at 21:09 UTC
I read about it, but the Partition Problem just tells you if the list of numbers can be partitioned into 2 halves that have the same sum. I'm not really interested into checking that. I don't mind them having the same or different sum. I only want the best possible partition. Thanks anyway. Note that the problem you are describing is (at best) just as hard as the original. Namely, if you can solve your problem, then you can solve the problem of finding a partition into equal halves by finding the best partition, and noting whether the difference in sums is 0. UPDATE: Oops, sorry, both moritz and jethro pointed that out already.	[reply]
Re^3: Divide array of integers into most similar value halves by jethro (Monsignor) on Sep 01, 2008 at 20:11 UTC
If you had an algorithm that found the best possible partition and there is one with difference 0 (for some array of integers) then your algorithm would find that one, otherwise you would find a difference>0. So your algorithm would be a solution to the partition problem.	[reply]
Re^3: Divide array of integers into most similar value halves by moritz (Cardinal) on Sep 01, 2008 at 20:09 UTC
But to find out if your solution is the best partition (and it's value is not sum/2) you have to check if there is a possible better partition, which means checking if the partition with the value sum/2 exists. Thus you have to solve the partition problem. D'oh.	[reply]