grouping objects to achieve a similar mean property for all groups

Posted by cytochrome on Stack Overflow See other posts from Stack Overflow or by cytochrome
Published on 2010-12-16T15:40:53Z Indexed on 2010/12/30 15:54 UTC
Read the original article Hit count: 208

Filed under:
|
|
|

I have a collection of objects, each of which has a numerical 'weight'. I would like to create groups of these objects such that each group has approximately the same arithmetic mean of object weights.

The groups won't necessarily have the same number of members, but the size of groups will be within one of each other. In terms of numbers, there will be between 50 and 100 objects and the maximum group size will be about 5.

Is this a well-known type of problem? It seems a bit like a knapsack or partition problem. Are efficient algorithms known to solve it?

As a first step, I created a python script that achieves very crude equivalence of mean weights by sorting the objects by weight, subgrouping these objects, and then distributing a member of each subgroup to one of the final groups.

I am comfortable programming in python, so if existing packages or modules exist to achieve part of this functionality, I'd appreciate hearing about them.

Thank you for your help and suggestions.

© Stack Overflow or respective owner

Related posts about python

Related posts about grouping