An allocation problem of people into groups getting them to meet as little as possible

I did some doodling and I think; If I understand you correctly, that you can do the following:

1. 28 people to do the 7 roles/7 games meeting other players only once.
2. If the position of a person in the following games is allocated to distinct roles then no person plays the same role in the games they play.

Python

# -*- coding: utf-8 -*-
"""
https://stackoverflow.com/questions/71143133/an-allocation-problem-of-people-into-groups-getting-them-to-meet-as-little-as-po

Created on Sat Feb 19 21:15:02 2022

@author: paddy3118

By hand to get the algo:
    0 roles, 0 people for 0 interactions
    1 role, 1 person
    2 roles, 3 people: p0+p1, p1+p2
    3 roles,   012, 134, 235 = 6 people
    4 roles,   0123, 1456, 2478, 3579 = 10 people
"""

from itertools import count


def new_person():
    yield from count()

def people_allocation(roles: int=4):
    games, new_p = [], count()
    for i in range(roles):
        game = []
        games.append(game)
        for j in range(i):
            game.append(games[j][i])
        for _ in range(i, roles):
            game.append(next(new_p))
    return games, next(new_p)

for roles in range(8):
    print(f"Roles = {roles}:")
    games, people = people_allocation(roles)
    print(f"  Takes {people} people in the following games")
    print('  ',
          ', '.join('+'.join(f"P{x}" for x in game) for game in games))

Output

Roles = 0:
  Takes 0 people in the following games
   
Roles = 1:
  Takes 1 people in the following games
   P0
Roles = 2:
  Takes 3 people in the following games
   P0+P1, P1+P2
Roles = 3:
  Takes 6 people in the following games
   P0+P1+P2, P1+P3+P4, P2+P4+P5
Roles = 4:
  Takes 10 people in the following games
   P0+P1+P2+P3, P1+P4+P5+P6, P2+P5+P7+P8, P3+P6+P8+P9
Roles = 5:
  Takes 15 people in the following games
   P0+P1+P2+P3+P4, P1+P5+P6+P7+P8, P2+P6+P9+P10+P11, P3+P7+P10+P12+P13, P4+P8+P11+P13+P14
Roles = 6:
  Takes 21 people in the following games
   P0+P1+P2+P3+P4+P5, P1+P6+P7+P8+P9+P10, P2+P7+P11+P12+P13+P14, P3+P8+P12+P15+P16+P17, P4+P9+P13+P16+P18+P19, P5+P10+P14+P17+P19+P20
Roles = 7:
  Takes 28 people in the following games
   P0+P1+P2+P3+P4+P5+P6, P1+P7+P8+P9+P10+P11+P12, P2+P8+P13+P14+P15+P16+P17, P3+P9+P14+P18+P19+P20+P21, P4+P10+P15+P19+P22+P23+P24, P5+P11+P16+P20+P23+P25+P26, P6+P12+P17+P21+P24+P26+P27

Assuming that n ≥ 78 or so, the following simple hill climbing algorithm with periodic restarts will return a solution.

The algorithmic idea is to initialize games where each player plays each role exactly once, then drive the number of conflicts to zero (where a conflict is a player playing two roles in a single game, or two players meeting each other more than once) by choosing two random games and a random role and swapping the players involved. We restart every 10⁷ steps because that seems to work well in practice.

Doubtless we could do a little better with constraint programming.

#include <algorithm>
#include <array>
#include <cstdlib>
#include <iostream>
#include <random>
#include <vector>

constexpr int r = 7;

int main() {
  int n;
  std::cin >> n;
  if (n <= r * (r - 1)) {
    return EXIT_FAILURE;
  }
  std::uniform_int_distribution<int> uniform_game(0, n - 1);
  std::uniform_int_distribution<int> uniform_role(0, r - 1);
  std::random_device device;
  std::default_random_engine engine(device());
  while (true) {
    std::vector<std::array<int, r>> games(n);
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < r; j++) {
        games[i][j] = (i + j) % n;
      }
    }
    int badness = 0;
    std::vector<std::vector<int>> pair_counts(n, std::vector<int>(n, 0));
    auto count = [&badness, &games, &pair_counts](int i, int j, int increment) {
      for (int k = 0; k < r; k++) {
        if (k == j) continue;
        auto [a, b] = std::minmax(games[i][j], games[i][k]);
        badness -= pair_counts[a][b] > (a != b ? 2 : 0);
        pair_counts[a][b] += increment;
        badness += pair_counts[a][b] > (a != b ? 2 : 0);
      }
    };
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < r; j++) {
        count(i, j, 1);
      }
    }
    for (long t = 0; t < 10000000; t++) {
      int i1;
      int i2;
      do {
        i1 = uniform_game(engine);
        i2 = uniform_game(engine);
      } while (i1 == i2);
      int j = uniform_role(engine);
      auto swap_players = [&]() {
        count(i2, j, -2);
        count(i1, j, -2);
        std::swap(games[i1][j], games[i2][j]);
        count(i1, j, 2);
        count(i2, j, 2);
      };
      int old_badness = badness;
      swap_players();
      if (old_badness < badness) {
        swap_players();
      } else if (badness < old_badness) {
        std::cerr << badness << '\n';
      }
      if (badness <= 0) {
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < r; j++) {
            if (j) std::cout << ' ';
            std::cout << games[i][j];
          }
          std::cout << '\n';
        }
        return EXIT_SUCCESS;
      }
    }
  }
}

Sample output:

21 38 61 75 77 2 22
70 31 75 7 15 59 69
28 52 29 73 59 23 40
61 45 16 65 35 15 55
12 72 44 45 46 14 10
57 1 3 38 11 6 49
20 6 7 26 0 74 18
54 73 67 58 6 55 75
73 77 63 36 3 0 45
37 57 55 28 34 43 7
17 46 36 66 16 7 48
74 9 24 22 17 73 15
36 50 4 69 28 65 6
59 62 12 32 24 20 51
38 8 59 17 10 19 39
6 53 21 70 13 71 56
55 33 49 59 5 27 36
15 71 33 54 43 18 29
60 36 8 40 71 51 67
19 49 9 34 45 53 60
41 26 73 21 72 35 19
14 64 42 15 57 63 62
44 11 23 27 9 16 21
2 7 68 9 63 52 54
35 18 2 3 60 64 17
29 17 50 41 31 61 57
47 10 32 25 75 28 35
30 48 64 6 32 39 44
46 22 71 35 20 31 11
43 76 41 11 47 60 14
56 2 1 33 74 10 37
51 41 39 0 33 70 34
32 5 18 31 23 76 68
65 43 53 8 27 46 73
63 44 26 5 70 24 28
62 75 66 71 44 3 41
16 69 54 13 22 41 5
58 19 52 57 36 22 70
42 25 22 44 55 56 76
4 30 35 51 76 13 9
72 13 17 62 40 77 43
53 16 10 68 50 58 64
64 47 70 55 38 40 20
50 59 14 48 1 9 71
40 63 19 76 69 1 12
24 35 69 56 68 57 27
67 34 15 72 56 66 32
68 3 46 37 25 21 59
77 54 47 19 4 44 31
76 67 38 46 52 50 33
25 15 77 1 51 26 23
3 61 40 4 53 5 74
45 51 74 29 48 68 47
75 0 57 23 30 8 72
13 27 28 14 19 67 2
9 20 72 42 65 33 3
49 58 48 20 41 37 77
22 12 37 67 39 47 53
26 42 11 61 37 36 13
1 60 5 39 29 75 46
48 40 65 10 54 34 26
23 66 60 50 42 54 24
8 74 13 63 49 32 50
27 29 58 12 7 38 42
7 4 45 24 64 25 8
71 24 30 47 2 49 16
31 28 56 60 12 48 0
10 23 62 49 67 69 61
34 21 31 30 58 62 1
66 70 27 18 61 30 25
0 37 76 64 66 29 65
69 39 43 2 26 45 58
39 65 25 74 62 11 52
5 56 20 52 14 17 30
33 68 6 77 8 12 66
11 55 51 53 18 72 63
52 32 0 43 21 42 4
18 14 34 16 73 4 38

Eventually I think I solved this problem. I explain it here to help any other person facing such a problem.

I used two "classical" algorithms.

1. try-and-error to get a first configuration of low quality, with iterations that tries first those players with fewest intearctions and which are already in more games

2. hill-climibing to improve quality of configuration (making swaps between a conflicting and not conflicting player, or two conflicting players if all players are conflicting) and selecting randomly, keeping the result of swap only if it increases quality - quality is worst number of conflicts (2 usually) and number of occurences)

I reach the following conclusion :

• always a solution above 100
• never a solution below 90

Thanks for all support you provided !