I have a collection of an arbitrary number of discrete "path lengths".

I'm interested in discovering some automated (preferably Excel or C++/C#/Java code rather than Matlab or similar) method of deciding how to group these lengths such that every group in the resulting set has as close to equal sum of lengths as possible. (Ideally in the first pass each group would have the minimum number of items in it as well, typically 2.) I'm happy to write the code myself if someone can sufficiently describe the algorithm.

For an input set with each item having roughly equal lengths (with normally distributed variation), the naive method is to sort them and then pair the longest with the shortest each time. This works sufficiently well, assuming that there were an even number of items.

Is there a better way to calculate this for an input set with a more uneven distribution (eg. some outliers that are a bit longer than the mean).

Assume that none of them can be divided or discarded, they can only be discretely summed. But they can be arbitrarily re-ordered.

The end goal is to apply this recursively, such that the final result is N groups in which each group has equal sums (or as close as possible) as every other group; and that within each group, as each item is visited, the running variance is minimised. (N is a small number chosen by the user.)

(This sounds tantalisingly like something that should already be a well-known problem, but I'm not thinking of the right tags / search terms.)


Your Answer

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

Browse other questions tagged or ask your own question.