0
$\begingroup$

I have a multiset, S, that contains N items that I wish to place into M different groups so that the sum of all N's in each group M is as evenly distributed as possible amongst all M's.

For example:

If my multiset were:

S = {6, 3, 5, 2, 7, 11, 2}, and number of groups M = 3,

I may expect a result like so (my long hand approximation):

M1 = {11, 2} sum of 13

M2 = {7, 5} sum of 12

M3 = {6, 3, 2} sum of 11

Is this something that could be done formulaically or would this be better approached algorithmically, and how under either case might I go about solving this problem?

EDIT:

Clarification.

Speaking in programming terms in which I can articulate myself more clearly, I have an array, S, that contains N integers, I am looking to find a method to split these distinct integers into M groups so that the sums of each group have as little difference between them as is possible based on the set of numbers in S.

The example above well demonstrates how such a group would occur under the test scenario given...

|cite|improve this question
$\endgroup$
  • $\begingroup$ When you say "the sum of all N's," presumably then these elements of $N$ are not just "items," but actual numbers? $\endgroup$ – Thomas Andrews Oct 19 '12 at 15:27
  • $\begingroup$ If you want the "absolute best" way, then you have to define what the "best" answer is. ""As evenly as possible" is not well-defined. On definition might be to minimize the standard deviation of the sums of each group. $\endgroup$ – Thomas Andrews Oct 19 '12 at 15:30
  • $\begingroup$ @ThomasAndrews apologies for any ambiguity. S = {6, 3, 5, 2, 7, 11, 2} refers an array holding 7 sub arrays, of which the count of the first array is 6, 3 the second. So by saying the sum of all N's in each group, I mean the total of a sub-collection of S, e.g. S[0] + S[1] = 9. Im just trying to split them into M even columns if that makes sense. $\endgroup$ – Larry B Oct 19 '12 at 16:05
  • $\begingroup$ @ThomasAndrews as evenly as possible was the best way I could think of, each M can't always be equal, so I'm trying to find the solution that has the least difference between sets of M $\endgroup$ – Larry B Oct 19 '12 at 16:06
1
$\begingroup$

The partition problem, which asks whether a given multiset of natural numbers can be partitioned into two submultisets with equal sums, is NP-complete. Since it can easily be reduced to your problem (by finding the most even distribution and checking whether it's perfectly even), your problem is also NP-complete. (In a nutshell, that means that it would be a revolution if you could find an algorithm that solves it in time polynomial in $N$.) However, the Wikipedia article seems to contain some efficient algorithms, some of which seem adaptable to your problem.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.