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

  • 0
    @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 M2012-10-19

1 Answers 1

1

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.