# Optimal dividing of K people into N groups

A teacher at a school has to do this on a regular basis. Let's say 12 students should be divided into either 4 groups of 3, or 3 groups og 4. Each student can pick up to 3 other students that person would most rather be with.

I tried to set this up as an undirected weighted graph, and implement shortest path algorithms, but the shortest path here doesn't ensure that as many students as possible get their top wish.

What algorithm should I look into here, in order to achieve to most optimal solution to a problem like this?

Here is a visualisation of the problem:

• There isn't an 'optimal solution' most likely. You will always have to overrule the wishes of some for the wishes of many. You have to be more specific - please provide a fitness function to optimize.
– orlp
Jan 9 '19 at 10:54
• It looks as though objective function should maximize the count of fulfilled wishes per person. Right? Should fairness be included in the game, in the way that if person 1 gets 3-of-3 wishes granted, person 2 shouldn't have only 1-of-3 wishes granted? Jan 9 '19 at 11:32
• @OzrenTkalcecKrznaric Yes, the goal is to maximize the count of fulfilled wishes pr. person. But at the same time, if person 1 gets all his wishes, the last person will most likely not get any of his wishes. So I'm guessing it would have round-based. First round - each person gets to pick one. if that choice is connected to 3 others, the second best options is explored and so on... Jan 9 '19 at 12:24
• @Nilzone-: Framing a problem like this is as an optimisation problem (which I think is the right approach here) requires, at minimum, a consistent way of comparing two solutions to see which is better (or if they are equally good). For a given solution $X$, let $s_1(X)$ be the number of people with at least 1 fulfilled wish, $s_2(X)$ the number of people with at least 2 fulfilled wishes, etc. For a criterion that incorporates fairness, I suggest: An optimal solution maximises $s_1(X)$, and among all such solutions maximises $s_2(X)$, ..., and among all such solutions maximises $s_N(X)$. Jan 9 '19 at 13:02
• It depends on what criterion you decide on (e.g. whether it's more important to satisfy a first choice than a second choice), but this is likely to be NP-hard for groups of size $\ge 3$, as it looks quite similar to the NP-hard problem 3-dimensional matching. OTOH, for groups of size 2 (where conveniently many of these distinctions go away), you can solve this exactly in polynomial time using an algorithm for maximum matching. Jan 9 '19 at 13:08

Solution in pseudocode:

initialize collection of persons (e.g. an array):
- each person itself is described by its position in collection
- each person itself contains collection of positions (e.g. an array)
that describe wished persons for the person to be grouped with
(example: persons = [[1,2], [0,2], [0,3], [0,2]])

initialize empty collection of groups (e.g. an array):
- each group itself is described by its position in collection
- each group itself contains collection of positions (e.g. an array)
that describe grouped persons

initialize number of persons per group (example: 2)
initialize total group count to be number of persons divided by number of persons per group (example: 2)
initialize constraint c1 as: any group shouldn't exceed the number of persons per group
initialize constraint c2 as: group count shouldn't exceed the number of total group count
initialize constraint c3 as minimum required of wishes granted per person in any group, for the solution to be valid (example: 1)
[*]initialize dictionary of solutions, where key is a pair (persons, groups), and value is a solution or an empty value

call group(persons, groups)

procedure group(persons, groups):
[*]if there is a pair (persons, groups) in dictionary of solutions
[*] return that solution

for each person (let's call it this-person)
for each person among this-persons wishes (let's call it wished-person)
if wished-person is already grouped in any of the groups
if this-person can be grouped in the same group with wished-person, at the same time satisfying c1
set new-groups as groups with this-person grouped accordingly
set new-persons as persons without this-person
else
nothing can be done with wished-person, so continue with the next wished-person
else
if both this-person and wished-person can be grouped in any group, at the same time satisfying c1 and c2
set new-groups as groups with this-person and wished-person grouped accordingly
set new-persons as persons without both this-person and wished-person
else
nothing can be done with wished-person, so continue with the next wished-person

if there are any other persons left in new-persons
set possible-solution to recursive call, group(new-persons, new-groups)
if possible-solution is not empty
[*]add item to dictionary of solutions, key is the pair (persons, groups), value is possible-solution
return it as a solution
else if all the groups satisfy c3
return new-groups as the solution

[*]add item to dictionary of solutions, key is the pair (persons, groups), value is empty
return empty value


The decision tree will exhaust all the possible paths towards the solution. However, if you use dynamic programming you can improve the performance by avoiding the execution of already known paths. The dynamic-programming part is marked with [*] in pseudocode.

You might further improve the performance by preferring least-popular persons over most popular when grouping.

Here's a Python implementation in case anyone needs it: https://repl.it/@OzrenTkalcec/Dividing-of-K-people-into-N-groups

Disclaimer: I'm not a data scientist, but I like to solve puzzles like this one :)

HTH

• Your code looks nice. However, explanations and ideas are valued way much more than actual code on this site in general unless the code is similar to pseudocode enough and short. This site is built for users to learn. While it is very handy to reuse other's code just by API, reading other's code is one of the toughest tasks in this world. Jan 16 '19 at 23:17
• @Apass.Jack - just substituted Python with pseudocode, hopefully that should do Jan 17 '19 at 12:42
• Yes, this answer has become much better with both clear pseudocode and a link to working code in a ready-to-run and easy-to-twiddle environment. So I just upvoted. The algorithm presented looks like exhaustive search to me. So it might not be the "most optimal solution". Jan 17 '19 at 13:08
• @Apass.Jack - that's true, and the solution can be improved as I've mentioned. However it wasn't in the code itself as I didn't have time to think about and/or write that. Well, now I've managed to include it. Jan 17 '19 at 14:10
• Sorry about that late response. Thank you very much! :) Jan 23 '19 at 8:17