I have been trying to solve this for quite a while without success. I have not found (I searched though) theory that could help me on wikipedia.
Here is the problem.
I have a group of n players (more than 7) I have a game (diplomacy for those who know !) that requires 7 players, one for these roles : E,F,G,I,A,R and T (countries in fact)
I want to set up a tournament (many games).
There will be n games.
(*) Every player gets into 7 different games, with different role each time
(**) Every game gets 7 different players
=> That is very easy to do.
However, when things get tough, is when you want to limit interactions between players. What I want is any player to interact (interact = play in same game) at most with one other player. (In other words, I want to prevent players from making such deals : "I help you in game A, you help me in game B")
So:
Question 1 : For which n is this possible ? (obviously at least 50)
Question 2 : When it is possible, how do you do it ?
Question 3 : What is the algo to minimize these interactions when it is not possible ?
For the record, I did implement a try-and-error program in python (using recursion), working quite well, but I never can get maximum intearctions between players limited to 1 (endless calculations)
thanks for any help !
PS This is no homework, it is for actually designing game tournaments :-)
CodePudding user response：
I did some doodling and I think; If I understand you correctly, that you can do the following:
- 28 people to do the 7 roles/7 games meeting other players only once.
- 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
CodePudding user response：
Assuming that n ≥ 78 or so, the following simple hill climbing algorithm with periodic restarts will return a solution. 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::random_device device;
std::default_random_engine engine(device());
std::uniform_int_distribution<int> uniform_game(0, n - 1);
std::uniform_int_distribution<int> uniform_role(0, r - 1);
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;
}
}
std::vector<std::vector<int>> pair_counts(n, std::vector<int>(n, 0));
for (int i = 0; i < n; i ) {
for (int k = 0; k < r; k ) {
for (int j = 0; j < k; j ) {
auto [a, b] = std::minmax(games[i][j], games[i][k]);
pair_counts[a][b] ;
}
}
}
int badness = 0;
for (int b = 0; b < n; b ) {
for (int a = 0; a <= b; a ) {
badness = pair_counts[a][b] > (a != b);
}
}
for (long t = 0; t < 10000000; t ) {
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;
}
int i = uniform_game(engine);
int l = uniform_game(engine);
if (i == l) continue;
int j = uniform_role(engine);
int old_badness = badness;
auto swap_players = [&]() {
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);
pair_counts[a][b]--;
badness = pair_counts[a][b] > (a != b);
}
for (int k = 0; k < r; k ) {
if (k == j) continue;
auto [a, b] = std::minmax(games[l][j], games[l][k]);
badness -= pair_counts[a][b] > (a != b);
pair_counts[a][b]--;
badness = pair_counts[a][b] > (a != b);
}
std::swap(games[i][j], games[l][j]);
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);
pair_counts[a][b] ;
badness = pair_counts[a][b] > (a != b);
}
for (int k = 0; k < r; k ) {
if (k == j) continue;
auto [a, b] = std::minmax(games[l][j], games[l][k]);
badness -= pair_counts[a][b] > (a != b);
pair_counts[a][b] ;
badness = pair_counts[a][b] > (a != b);
}
};
swap_players();
if (old_badness < badness) {
swap_players();
} else if (badness < old_badness) {
std::cerr << badness << '\n';
}
}
}
}
Sample output:
66 3 28 7 14 39 30
74 73 16 33 35 69 11
23 26 72 3 75 12 4
20 74 40 15 67 8 60
21 51 67 76 70 41 63
26 55 37 66 36 73 0
40 9 26 5 28 62 32
10 5 22 24 3 60 52
50 36 27 21 18 64 69
18 40 48 41 42 56 44
17 29 2 46 58 9 15
65 60 54 56 55 57 14
16 13 52 54 32 4 39
56 69 51 39 72 37 19
60 7 36 77 38 51 46
19 12 57 22 40 16 70
62 66 18 59 60 2 25
53 21 33 60 31 48 72
55 67 47 25 30 17 22
30 61 60 75 29 68 35
76 57 39 49 24 25 26
69 44 63 2 65 26 61
72 14 58 67 61 32 59
22 6 49 36 54 72 2
43 52 30 12 20 44 64
48 59 75 9 49 47 13
7 22 73 42 63 23 62
49 30 19 23 21 5 74
75 17 66 32 74 43 27
3 53 38 20 45 70 55
77 31 65 13 66 50 23
0 68 64 74 9 65 3
51 4 20 61 47 0 18
37 15 4 62 64 31 49
34 1 62 14 51 11 75
38 33 15 26 56 59 68
42 77 21 11 2 52 37
2 27 68 40 13 7 24
59 45 34 8 4 35 21
25 16 9 37 10 53 7
13 62 10 43 0 67 56
28 70 74 4 44 58 36
63 25 14 71 5 13 12
64 48 32 55 23 46 76
27 39 71 38 41 61 9
44 11 45 72 76 66 5
1 24 53 69 12 42 66
6 20 7 50 26 34 48
68 37 70 47 8 71 54
47 23 11 53 15 28 43
29 38 12 28 73 54 67
32 47 44 57 6 21 73
61 8 23 17 1 36 16
39 58 0 63 77 1 40
15 10 77 73 71 30 45
70 18 17 34 39 10 33
67 34 5 65 46 27 42
12 32 50 45 33 49 51
33 19 46 44 62 3 71
14 35 31 6 17 24 38
24 64 29 16 34 77 47
52 0 8 27 48 19 29
36 65 24 19 11 20 41
8 42 13 30 57 38 58
57 41 69 0 7 45 17
58 71 35 48 43 22 65
71 49 55 52 69 40 34
35 72 25 70 27 15 1
11 63 3 31 59 29 57
45 56 61 64 25 6 28
9 54 76 35 19 18 77
31 28 42 10 68 76 20
54 46 59 1 50 74 10
46 75 6 18 53 63 8
4 50 41 68 22 14 53
73 76 56 58 52 75 50
5 2 43 51 16 55 31
41 43 1 29 37 33 6