Can't say that it's efficient, but it's thorough:
Generate all the possible combinations of the integers (not
permutations), and compare their sums to each other. Keep in mind that
the integers you *don't* pick for one sub-group, are automatically part
of the second sub-group, which was "left behind".
The other way is "intelligent guessing", but from what I was able to
find on the web, that algorithm has no better than an 86% chance of
being correct.
When I tested one of these "guessers", it ran very quickly, but on
10,000 different combinations of integers, it found only 68% correctly.
Basically, it added up the integers, then divided it in half, and tried
to "pack" each half, with the "biggest values first" methodology.
I wasn't impressed with it's accuracy, but it WAS definitely fast!
I wrote a program for this, which basically searches thru the
combination search space working like an odometer on your car. It found
every combination that matched, but if you had to use it on an array of
40 numbers or more - you'll need a good deal of patience, or a very
fast computer.
Here's some info for you:
How to calculate the # of combinations:
(not permutations, which counts the same data, in a different order,
(so {1, 2} != {2, 1}), as a different thing. To a combination guy,
{1,2} == {2,1}, and someone just forgot to sort the second data set, in
the same way as the first one.
Our equation is, n! / r!(n-r)!, where n = number of array values, r =
number chosen out of the set, and '!' indicates the number to it's
left, is to be a factorial - so
7! = 7*6*5*4*3*2*1 == 5040.
When we select just one number from a set of seven, our possible
choices (although obvious) are: 7!/1!(7-1)! or, 7!/1!*6! or 7!/6! or
5040/720 == 7 (big surprise, right?). BUT THAT'S
NOT ALL!! <grin> To find ALL the unique combo's for 7 numbers, we
*also* have to add up all the combo's that might have TWO numbers, then
add up all the combo's that have THREE numbers, then four, and right on
up to seven. Total is 126 unique combos for all the subsets, and then
one more for the set with all seven members in it, for a grand total of
127 combo's.
It seems that a much better program would examine the integers in the
set, and find good sub sets that could be used instead of dividing the
total sum by two, as a mid-point.
Perhaps that' one reason the guessing program I tested wasn't that
successful. Somehow, the program needs to learn something about the
specific set of numbers it has, in order to guess at a good goal for
each of the two halves of the set.
Let us know what you find. I'm a hobby programmer, so any theory for
this is quite new to me.
Good luck, valpa!
Adak
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
