Organisation tournoi multisports avec 7 équipes

Tu dis que chaque équipe doit jouer au moins une fois contre chacune des autres? Faisons un petit diagramme avec une matrice diagonale:
La première ligne et la première colonne sont pour numéroter les  équipes.
\ 1 2 3 4 5 6 7                                                                                                          
1 *                                                                                                                     
2 1 *                                                                                                                   
3 1 2 *                                                                                                                 
4 1 2 3 *                                                                                                               
5 1 2 3 4 *                                                                                                             
6 1 2 3 4 5 *                                                                                                           
7 1 2 3 4 5 6 *                                                                                                         
L'astérisque est pour montrer qu'une équipe ne joue pas contre elle-même.
On voit qu'il y aura 21 parties en tout. On a 3 terrains. Donc chaque terrain sera utilisé 7 fois.
Et on répète pour chaquun des  6 sport.
Est-ce que ça répond à tes critères?
On place sur chaque terrain deux équipes qui ne sont pas sur un autre terrain (au début tous les terrains sont libres).
Et on efface chacune des 3 case après les parties.
On recommence tant qu'il y a des cases dans la matrice.

bonjour,

Tu as besoin de plus de 6 tours pour réaliser cela.  En 6 tours, chaque équipe n'aura même pas joué 6 fois, donc n'aura pas rencontré chaque autre équipe. Ni joué à chaque sport.

Bonjour,

Est-ce que le but est de trouver à chaque slot de temps quels matchs doivent être joués ? Le problème a bien entendu plein de symétries puisque à une renumérotation prête des équipes, on peut trouver un autre planning de matchs.

Le problème a évidemment une solution (dans le pire des cas, on peut faire à chaque slot de temps un seul match parmi ceux listés par pierrot, soit 21 slots de temps).

Si on omet la contrainte des terrains, pour résoudre le problème en moins de slots de temps, je pense qu'un algorithme glouton qui garde trace des matchs déjà joué est suffisant. Je suppose que chaque match dure un slot de temps.

• Match joués = {}
• t = 0
• Tant que |Match joués| != 21
  • Réinitialiser équipes disponibles = {1, ..., 7}
  • Pour i = 0 ... 6
    • Si i n'est pas disponible
      • Continuer
    • Trouver une équipe disponible j telle que ni (i, j) ni (j, i) n'est pas dans Matchs joués
    • Si j existe:
      • Ajouter (i, j) -et/ou (j, i)- à Match joués : le match (i, j) est joué à l'instant t
      • Retirer i et j des équipes disponibles
    • i ++
  • t ++

Une fois que tu as décidé des matches, je pense que tu peux résoudre la problématique des jeux associés à chaque match dans un second temps.

Il est probable en tout cas sur cette instance qu'un algorithme glouton du même genre soit suffisant. Au pire du pire ton problème se résout avec un ILP (Integer Linear Program) ou un CSP (Constraint Satisfaction Program), mais cela présuppose que tu as des notions en recherche opérationnelle (la branche des maths qui s'occupe des problèmes d'optimisation).

Bonne chance

On est tous d'accord qu'il faut plus de 6 "tours" pour jouer toutes les parties pour les 6 sports en question.
On peut le voir comme un problème d'analyse combinatoire.
Une équipe ne peut pas jouer contre elle-même. L'équipe A ne peut pas jouer contre A.
De même, il y a symétrie. Si A joue contre B, c'est la même chose de dire que B joue contre A.
Il faut donc calculer le nombre de combinaisons de 2 valeurs parmi N (ici N vaut 7).
C(7, 2) vaut justement 21 (7!/(5!2!) )
On peut faire une liste de ces paires de nombres et faire en sorte qu'il n'y ait pas deux fois la même paire (ou son équivalent).
Suivant le langage utilisé, on pourrait avoir une liste de tuples ou un tableau 2D donnant ainsi les paires.
Ici, on est chanceux, 21 se divise justement par 3. On peut parcourir la liste et assigner les équipes par groupes de 3 paires.
Cela fera exactement 7 tours de 3 parties ou terrains. Et on recommence pour chaque sport. Donc au total 21*6 = 126 parties ou 42 tours complets.
Supposons que le nombre d'équipes soit de 8 au lieu de 7.
Le nombre de combinaisons sera donc C(8, 2) = (8!/(6!2!) ) = 28, qui ne se divise pas par 3.
On peut faire comme pour l'autre liste en assignant une paire à chaque terrain par groupe de 3 paires.
Cela fera 27 paires groupées par 3. donc 9 tours.
Et que fait-on avec la 28ième paire?
On la place sur le premier terrain et on retourne au début de la liste mais on passe au sport suivant.
On aura virtuellement une liste de 28*6 (168) parties-paires, donc 168/3 = 56 ttours complets.
Si le nombre de sports était de 7 au lieu de 6, on aurait au total 28*7 = 196 parties-paires.
Dans ce cas, on aurait 65 tours complets avec 3 terrains et un tour avec un seul terrain.

Bonjour,

Je vous propose cette formulation ILP que j'espère complète et correcte. On définit T_max a priori (par exemple 24) et on regarde si le solveur trouve une solution, sinon on augmente T_max.

Notations : (je donne les domaines de définition ici ; pour alléger les notations, je ne les rappellerai donc ni dans les sommes, ni les quantificateurs des contraintes puisque ce sont implicitement toujours les mêmes):

• i, j: les indices des équipes dans {1...7}
• k: les indices des sports à valeur dans {1...6}
• t: les indices du temps à valeur dans {1...T_max}

Variables de décisions (pour chaque valeur de i, j, k, t) :

• Xijt : les équipes i et j se rencontrent au temps t pour faire le sport k, à valeur dans {0, 1}
• Yikt : l'équipe i joue au sport k au temps t, à valeur dans {0, 1}

Fonction objectif :

• min sum_t sum_i sum(i <j) Xijt // Minimiser le nombre de rencontres (on veut éviter que des paires d'équipe (i, j) se rencontrent plusieurs fois "pour le fun")

Contraintes (linéaires) :

• Xiit = 0 // L'équipe i ne peut pas se rencontrer elle-même
• Pour tout i, pour tout j != i, pour tout t : Xijt = Xjit // Si i rencontre j au temps t, alors l'équipe j rencontre i au temps t également 
• Pour tout i, sum_k Yikt <= 1 // Chaque équipe i joue à au plus un sport au temps t
• Pour tout i, pour tout j != i, pour tout k : Yikt + Yijt >= 2 * Xijt // Si i et j se rencontrent à l'instant t, alors elles pratiquent toutes les deux le sport k
• Pour tout t: sum_i sum_(i<j) Xijt <= 3 // Au plus 3 rencontres à chaque temps t
• Pour tout i, pour tout t: sum_k Yikt <= 1 // Chaque équipe i joue à au plus 1 sport à chaque instant t
• Pour tout i: sum_t sum_k Yikt >= 6 // Chaque équipe i joue aux 6 sports

Implémentation

D'un point de vue pratique, il existe de nombreux solveurs ILP. En python par exemple, scipy fournit une fonction pour résoudre un MILP (donc un ILP), à savoir scipy.optimize.milp.

Il existent de nombreux autres solveurs, pas seulement en python. Parmi les plus connus, on peut notamment citer Ilog Cplex (payant), Coin-OR (équivalent de Cplex libre) utilisables en C++ et en Java.

Remarques

On peut probablement faire quelques relaxations linéaires (par exemple dire que les Xijt et/ou les Yikt sont dans [0, 1] au lieu de {0, 1}) afin de réduire le nombre de variables entières (qui deviennent de facto continue) et ainsi accélérer significativement la résolution. On espère en faisant une telle relaxation toujours trouver une solution entière (si ça n'est pas le cas, on les repasse dans le domaine discret). Ça vaut alors le coup de regarder scipy.optimize.linprog.

Bonne chance

Voici un exemple de comment organiser ce tournoi en 24 parties, donc en 8 tours:

Au tour 0, les équipes 0 et 1 jouent au jeu 0.
Au tour 0, les équipes 2 et 3 jouent au jeu 0.
Au tour 0, les équipes 4 et 5 jouent au jeu 0.
Au tour 1, les équipes 1 et 2 jouent au jeu 1.
Au tour 1, les équipes 3 et 4 jouent au jeu 1.
Au tour 1, les équipes 5 et 6 jouent au jeu 1.
Au tour 2, les équipes 0 et 2 jouent au jeu 2.
Au tour 2, les équipes 1 et 3 jouent au jeu 2.
Au tour 2, les équipes 4 et 6 jouent au jeu 2.
Au tour 3, les équipes 0 et 3 jouent au jeu 3.
Au tour 3, les équipes 1 et 6 jouent au jeu 3.
Au tour 3, les équipes 2 et 5 jouent au jeu 3.
Au tour 4, les équipes 0 et 4 jouent au jeu 4.
Au tour 4, les équipes 1 et 5 jouent au jeu 4.
Au tour 4, les équipes 3 et 6 jouent au jeu 4.
Au tour 5, les équipes 0 et 5 jouent au jeu 5.
Au tour 5, les équipes 1 et 4 jouent au jeu 5.
Au tour 5, les équipes 2 et 6 jouent au jeu 5.
Au tour 6, les équipes 0 et 6 jouent au jeu 0.
Au tour 6, les équipes 2 et 4 jouent au jeu 4.
Au tour 6, les équipes 3 et 5 jouent au jeu 5.
Au tour 7, les équipes 0 et 6 jouent au jeu 1.
Au tour 7, les équipes 2 et 4 jouent au jeu 3.
Au tour 7, les équipes 3 et 5 jouent au jeu 2.