génération des matchs d'une compétition

parsy · 25/02/2008, 13h55

Bonjour

je cherche un algorithme pour déterminer les journées d'une compétition de n équipes , chaque équipe jouant une fois contre les autres équipes sur un terrain neutre

pour n égal à 4

on a 3 journées

Code :

journée 1
équipe 1 contre equipe 2
équipe 3 contre equipe 4
journée 2
équipe 1 contre equipe 3
équipe 2 contre equipe 4
journée 1
équipe 1 contre equipe 4
équipe 2 contre equipe 3

pour n = 6

Code :

journée 1
équipe 1 contre equipe 2
équipe 3 contre equipe 4
équipe 5 contre equipe 6
journée 2
équipe 1 contre equipe 3
équipe 2 contre equipe 5
équipe 4 contre equipe 6
journée 3
équipe 1 contre equipe 4
équipe 2 contre equipe 6
équipe 3 contre equipe 5
journée 4
équipe 1 contre equipe 5
équipe 2 contre equipe 4
équipe 3 contre equipe 6
journée 5
équipe 1 contre equipe 6
équipe 2 contre equipe 3
équipe 4 contre equipe 5

...

merci de votre aide

merci de votre aide

Zavonen · 26/02/2008, 03h55

Cela revient à générer les n(n-1) paires que l'on peut former dans un ensemble à n éléments.
On peut procéder itérativement
Considérer tous les nombres binaires à n chiffres et ne sélectionner que ceux qui ont 2 fois et 2 fois seulement le chiffre 1
Exemple pour 4
0011
0101
0110
1001
1010
1100
Ou bien récursivement
Les paires de {1;2;....;n}
s'obtiennent en prenant d'abord toutes les paires de {1;2;...;n-1}
puis tous les singletons du même ensemble auxquels on adjoint le dernier élément n.

pseudocode · 26/02/2008, 10h40

Round Robin Tournament Scheduling

Nemerle · 26/02/2008, 14h54

Exemple pour n=8: tu pars de la 1ière journée

12 (1 contre 2)
34 (3 contre 4)
56 etc..
78

Ensuite , pour les journées suivantes, tu fixes l'équipe 1 et tu fais tourner les autres d'un cran dans le sens des aiguilles d'une montre par exemple:

Jr2:

13
52
74
86

Jr3:

15
73
82
64

...

Une fois que tu reviens à la position du 1ier jour, c'est fini. J'ai pas trouvé plus rapide

ZZelle · 26/02/2008, 15h22

Si n est impair, ça marche aussi ? (remarque, ça doit marcher si on rajoute une n+1-ième équipe représentant la fois où l'équipe ne joue pas)

Je me suis tjrs dit que c'était pour ça qu'on avait intégré l'Italie dans le tournoi des nations

pseudocode · 26/02/2008, 15h24

Citation:

Envoyé par ZZelle

Si n est impair, ça marche aussi ?

il suffit d'ajouter une equipe "null", pour se retrouver dans le cas "pair".

(l'histoire ne dit pas qui joue le role de l'equipe null)

Nemerle · 26/02/2008, 16h36

LE PSG??????

ALLEZ L'OL!!

26/02/2008, 10h40	#3
pseudocode Rédacteur/Modérateur Nom : Xavier Philippeau Date d'inscription: décembre 2006 Localisation: Montpellier Âge: 37 Messages: 6 864	Round Robin Tournament Scheduling __________________ ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

26/02/2008, 14h54	#4
Nemerle Membre émérite Date d'inscription: octobre 2003 Âge: 39 Messages: 975	Exemple pour n=8: tu pars de la 1ière journée 12 (1 contre 2) 34 (3 contre 4) 56 etc.. 78 Ensuite , pour les journées suivantes, tu fixes l'équipe 1 et tu fais tourner les autres d'un cran dans le sens des aiguilles d'une montre par exemple: Jr2: 13 52 74 86 Jr3: 15 73 82 64 ... Une fois que tu reviens à la position du 1ier jour, c'est fini. J'ai pas trouvé plus rapide __________________ Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

26/02/2008, 16h36	#7
Nemerle Membre émérite Date d'inscription: octobre 2003 Âge: 39 Messages: 975	LE PSG?????? ALLEZ L'OL!! __________________ Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

26/02/2008, 03h55	#2
Zavonen Rédacteur Date d'inscription: novembre 2006 Localisation: Boulogne sur Mer Âge: 62 Messages: 1 423	Cela revient à générer les n(n-1) paires que l'on peut former dans un ensemble à n éléments. On peut procéder itérativement Considérer tous les nombres binaires à n chiffres et ne sélectionner que ceux qui ont 2 fois et 2 fois seulement le chiffre 1 Exemple pour 4 0011 0101 0110 1001 1010 1100 Ou bien récursivement Les paires de {1;2;....;n} s'obtiennent en prenant d'abord toutes les paires de {1;2;...;n-1} puis tous les singletons du même ensemble auxquels on adjoint le dernier élément n.

26/02/2008, 15h22	#5
ZZelle Futur Membre du Club Date d'inscription: avril 2007 Messages: 36	Si n est impair, ça marche aussi ? (remarque, ça doit marcher si on rajoute une n+1-ième équipe représentant la fois où l'équipe ne joue pas) Je me suis tjrs dit que c'était pour ça qu'on avait intégré l'Italie dans le tournoi des nations

		Forum des professionnels en informatique > Autres langages > Algorithmes > Mathématiques
génération des matchs d'une compétition

Outils de la discussion
Afficher une version imprimable Envoyer un lien vers cette page par email