I am searching for a consolidated model to group n items in x groups. Do you know how to find on the web some resources on the above subject?
In my idea it can be something like: I have 4 persons and 2 groups of 2 persons each. The "friendship" level can be set on a range from 10 to -10
A B C D A X 9 0 -1 B 9 X 5 -5 C 0 5 X 0 D -1 -5 0 X
would group A&B (friendship level 9) and C&D (friendship level 0) because it maximize the overall friendship level respecting the constraint over groups (9 + 0 = 9 best possible choice).
To sum up
n items with measures associated (with must and mustn't group with...)
x groups (each with its own size i.e. group1 -> 5 items, group2 --> 15 and so on)
- Best or sub optimal choice(s)
So a most complex example can be:
I have 16 persons to divide as:
- Group 1: 2 persons
- Group 2: 2 persons
- Group 3: 4 persons
- Group 4: 8 persons
You have the same friendship level, but in my idea I would add or a side-logic for forcing grouping and ungrouping or use a fake level (say 10k or -10k) to enforce the same behaviour.
EDIT @Joriki: for groups of more than 2 persons logic does not change, meaning that if AB=5, BC=2, AC = -1, friendship level is 6 (=5+2+(-1))
EDIT2: In my example I was using sums, but every suggestion is welcome. Joriki pointed out the use of products. I think it is a good idea indeed but then negative values won't be used any longer.
Any hint on a model / algorithm that can be adapted to the above case?