splitting a group by preferences

Question

Am a C# rookie trying to help a friend programatically take a group of twenty people (labelled 1 - 20) and spilt them into five subgroups of four each based upon expressed preferences of who those people wish to be with. Each person in the group of 20 could express 0, 1, 2, 3, or 4 preferences. For example, person 1 could select 0 (no preference of who they are with), or 14 (in a group with person 14) or could express to be in a group with persons 14, 20, 6, and 7. Ideally each person with a preference would be in a group with at least one choice. Ideas on an algorithm? Thanks.

Answer 1

The problem you are having is not really related to C#, the algorithm is independent on the language.

A classic implementation for this problems is backtracking.

More info:

• Constraint satisfaction problems on Wikipedia
• Recommended: Chapter 5 from Artificial Intelligence - A Modern Approach 2nd edition

Another approach (I would go for this): Genetic Algorithms.

Answer 2

This is probably a it too much to ask at SO, but think the problem is quite interesting, so here are some thoughts.

As Victor Hurdugaci says, this is mainly an algorithmic problem independent of the language (although I'd love to see my example below implemented with LINQ!)

The problem described in your question cannot yield a perfect result, i.e. it's an optimization problem (so you cannot solve it with a constraint statisfaction algorithm). You have to find an algorithm that finds the best result from the set of all possible results based on some function that indicates how good a result is (called fitness function).

Naive Brute force Solution (pseudo-code)

We start with the set of people (here: 4 to simplify things):

people = { a, b, c, d }

We can find all possible subgroups of a fixed size (here: 2) using a choose operator:

groups = people.choose(2)  // = { {a,b} {a,c} {a,d} {b,c} {b,d} {c,d} }

We can find all possible combinations of subgroups using the choose operator again:

combi = groups.choose(4/2) // = { {ab,ac} {ab,ad} {ab,bc} {ab,bd}
                           //     {ab,cd} {ac,ad} {ac,bc} {ac,bd}
                           //     {ac,cd} {ad,bc} {ad,bd} {ad,cd}
                           //     {bc,bd} {bc,cd} {bd,cd} }

Obviously people cannot be in two groups at the same time, so we remove all invalid combinations:

combi2 = combi.select(g => g.bigUnion().size == 4)
                           // = { {ab,cd}, {ac,bd}, {ad,bc} }

Now you have to find the "best" item based on some fitness function, i.e. the combination that scores best considering the preferences.

result = combi2.maximumBy(g => fitness(g))

For example, if a has a preference for b, and b, c and d do not have any preferences, then calculateScore should return a higher score for {ab,cd} than for {ac,bd} and {ad,bc}.

Improved Solution

There a several algorithms that deal with this kind of optimization problem. I think a Hill climbing algorithm would suit here well.