Put N items into M groups such that the sums of the N's in every M are as even as possible

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

-

When you say "the sum of all N's," presumably then these elements of $N$ are not just "items," but actual numbers? – Thomas Andrews Oct 19 '12 at 15:27
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. – Thomas Andrews Oct 19 '12 at 15:30
@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. – Gareth Harding Oct 19 '12 at 16:05
@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 – Gareth Harding Oct 19 '12 at 16:06

1 Answer

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.

-

Thank you very much for this insight. – Gareth Harding Oct 22 '12 at 9:48
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 2, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9613750576972961, "perplexity_flag": "middle"}