# Algorithm to group entities into variable sized groups based on attribute

I have the following problem:

There are n entities (persons) having a common attribute (weight) and I need to build weight categories (this is for a sports event) grouping people based on their weight. The weight of the people in one group should be as equal as possible.

Problem/Opportunity is that the group size can vary. The groups should usually hold 4 persons, but can be 5 or 3 persons as well if that fits better. 2 or 1 only in exceptions, usually at the upper and lower end.

It sounds somehow like a clustering problem, but I could not find a variant matching this kind of problem.

Example:

• Person 1: 15kg
• Person 2: 20kg
• Person 3: 21kg
• Person 4: 27kg
• Person 5: 27.5kg
• Person 6: 27.7kg
• Person 7: 28kg
• Person 8: 28.1kg
• Person 9: 29kg

This should result in 4 groups:

1: 1 2: 2+3 3: 4-6 4: 7-9

Even though group 3 could also have 4 competitors, group 4 would then be left with two only.

I can probably come up with more rules, but my main question is if there is a algorithm/problem I can use as start point.

• Have you checked the article on Wikepedia, cluster analysis? Could you edit your question to show why clustering algorithms you have check do not fit? – John L. Feb 27 '19 at 14:23
• It's not clear how the people's weights must affect the groups. As such, the problem doesn't seem to be complete yet. Saying that the weight should be as equal as possible isn't enough, because you haven't told us how you want to measure the amount of inequality -- there are many possible ways. Can you define an objective function that measures how good a candidate grouping is? Please edit the question to describe the additional requirements. – D.W. Feb 27 '19 at 15:52
• @D.W. Maybe I misunderstood, but the "weight of the people in one group should be as equal as possible" in the question seems to be the criterion to evaluate a possible distribution as more desirable than others, and seems consistent with the example provided. OP : is it? – YSharp Mar 1 '19 at 18:49
• @YSharp, like I wrote before, there are multiple possible ways to measure how inequal a candidate grouping is, and different choices for that will lead to different algorithms and different solutions. It's not obvious to me what the poster has in mind. (Is it the standard deviation of weights in each group, then averaged over all groups? The max - min for each group, averaged over all groups? The largest value of standard deviation in any group? The largest value of max-min in any group? Something else?) – D.W. Mar 1 '19 at 19:10
• Also, the question says "2 or 1 only in exceptions", but it doesn't say under what circumstances we are allowed to make exceptions. (What if my algorithm always chooses 2 or 1 whenever that's convenient, and calls it an exception? As we know, if there are no limits on when we can declare an exception, then it effectively no longer is an exception and becomes the norm -- so it's important to declare under what specific conditions an exception is allowed to be declared.) – D.W. Mar 1 '19 at 19:12