Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Input Data:

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

Output data:

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


share|cite|improve this question
you have an example of what it can't be, but do you have an example of what it can be? I don't understand what you're trying to do. – Patrick Da Silva Jul 18 '11 at 8:45
Sorry, it was a typo. I edit it now! – Mauro Jul 18 '11 at 8:51
I removed the model-theory tag, as it is intended to refer to this. – t.b. Jul 18 '11 at 9:47
I don't understand your example. It might clarify the question if you explain why A & B and C & D would be grouped together. Also the description under "Input Data" could use some clarification/explication. – joriki Jul 18 '11 at 9:55
Yeah, it's still unclear. Can you give more examples or give us an idea of what does those measures mean and how does the group gets chosen? I know that's almost actually your question, but we don't understand what you want to find (at least me and joriki!) – Patrick Da Silva Jul 18 '11 at 9:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.