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