This is my first question. I tried to find an answer for 2 days but I couldn't find what I was looking for.

Question: How can I minimize the amount of matches between students from the same school

I have a very practical case, I need to arrange a competition (tournament bracket) but some of the participants might come from the same school. Those from the same school should be put as far as possible from each other

for example: {A A A B B C} => {A B}, {A C}, {A B}

if there are more than half participants from one school, then there would be no other way but to pair up 2 guys from the same school.

for example: {A A A A B C} => {A B}, {A C}, {A A}

I don't expect to get code, just some keywords or some pseudo code on what you think would be a way of making this would be of great help!

I tried digging into constraint resolution algorithms and tournament bracket algorithms, but they don't consider minimising the amount of matches between students from same school.

Well, thank you so much in advance!

A simple algorithm (EDIT 2)

From the comments below: you have a single elimination tournament. You must choose the places of the players in the tournament bracket. If you look at your bracket, you see: players, but also pairs of players (players that play the match 1 against each other), pairs of pairs of players (winner of pair 1 against winner of pair 2 for the match 2), and so on.

The idea

• Sort the students by school, the schools with the more students before the ones with the less students. e.g A B B B B C C -> B B B B C C A.
• Distribute the students in two groups A and B as in a war card game: 1st student in A, 2nd student in B, 3rd student in A, 4th student in B, ...
• Continue with groups A and B.

You have a recursion: the position of a player in the level k-1 (k=n-1 to 0) is ((pos at level k) % 2) * 2^k + (pos at level k) // 2 (every even goes to the left, every odd goes to the right)

Python code

Sort array by number of schools:

assert 2**math.log2(len(players)) == len(players) # n is the number of rounds
c = collections.Counter([p.school for p in players])
players_sorted_by_school_count = sorted(players, key=lambda p:-c[p.school])

Find the final position of every player:

players_sorted_for_tournament = [-1] * 2**n
for j, player in enumerate(players_sorted_by_school_count):
    pos = 0
    for e in range(n-1,-1,-1):
        if j % 2 == 1:
            pos += 2**e # to the right
        j = j // 2
    players_sorted_for_tournament[pos] = player

This should give groups that are diverse enough, but I'm not sure whether it's optimal or not. Waiting for comments.

First version: how to make pairs from students of different schools

Just put the students from a same school into a stack. You have as many stack as schools. Now, sort your stacks by number of students. In your first example {A A A B B C}, you get:

A
A B
A B C

Now, take the two top elements from the two first stacks. The stack sizes have changed: if needed, reorder the stacks and continue. When you have only one stack, make pairs from this stack.

The idea is to keep as many "schools-stacks" as possible as long as possible: you spare the students of small stacks until you have no choice but to take them.

Steps with your second example, {A A A A B C}:

A
A
A
A B C => output A, B

A
A
A C => output A, C

A
A => output A A

It's a matching problem (EDIT 1)

I elaborate on the comments below. You have a single elimination tournament. You must choose the places of the players in the tournament bracket. If you look at your bracket, you see: players, but also pairs of players (players that play the match 1 against each other), pairs of pairs of players (winner of pair 1 against winner of pair 2 for the match 2), and so on.

Your solution is to start with the set of all players and split it into two sets that are as diverse a possible. "Diverse" means here: the maximum number of different schools. To do so, you check all possible combinations of elements that split the set into two subsets of equals size. Then you perform recursively the same operation on those sets, until you arrive to the player level.

Another idea is to start with players and try to make pairs with other players from other school. Let's define a distance: 1 if two players are in the same school, 0 if they are in a different school. You want to make pairs with the minimum global distance.

This distance may be generalized for the pairs of players: take the number of common schools. That is: A B A B -> 2 (A & B), A B A C -> 1 (A), A B C D -> 0. You can imagine the distance between two sets (players, pairs, pairs of pairs, ...): the number of common schools. Now you can see this as a graph whose vertices are the sets (players, pairs, pairs of pairs, ...) and whose edges connect every pair of vertices with a weight that is the distance defined above. You are looking for a perfect matching (all vertices are matched) with a minimum weight.

The blossom algorithm or some of its variants seems to fit your needs, but it's probably overkill if the number of players is limited.