XL 2013 Challenge : un tableau minimisant les doublons !

[Douvid]

Bonjour à tous,

Je bloque depuis quelques jours sur un problème suffisamment urgent pour que je m'inscrive sur ce site et sollicite votre aide. Le problème paraissait simple à résoudre au départ mais vous allez voir que ce n'est pas si facile que cela !

Il me reste 3 jours pour organiser un tournoi, dans lequel 9 équipes (numérotées de 1 à 9) doivent s'affronter, sur 8 jeux (de A, à H). Le principe est : chaque équipe doit jouer minimum une fois contre chaque autre équipe, et doit passer sur les 8 jeux. Tous les jeux se jouent 1 équipe contre 1 autre à chaque fois, et une équipe sera donc sortante à chaque tour. Les duels entre équipes se feront de manière simultanée, il y'aura donc à chaque tour 4 jeux joués simultanément, et 4 jeux non utilisés. J'ai déjà trouvé la solution pour que chaque équipe se rencontre 1 fois, et donc il y'aurait 9 tours avec à chaque fois une équipe différente qui sort. Le problème est que je n'arrive pas à répartir ces duels sur les 8 jeux, de sorte à ce que chacune des équipes fasse au moins une fois chaque jeu. Vous comprenez ? C'est un bête tableau à double entrée, où toutes les cases ne sont pas à remplir et où il ne doit pas y avoir le même n° d'équipe sur une colonne (ça c'est déjà fait) et sur une ligne (ou au pire en minimisant le nombre de répétitions). Le nombre d'équipes et le nombre de jeux ne peuvent être changés, le nombre de tours peut l'être si ça peut aider...

Je vous joins le fichier Excel pour illustrer. Je compte réellement sur vous pour m'aider, je suis au bout de mes capacités intellectuelles sur ce problème je crois...

Merci d'avance à toute la communauté !

Bien à vous,

David

 

[patricktoulon]

ce que tu souhaite faire est tout bonnement impossible a faire pour la simple et bonne raison que ton règlement d'une équipe sortante
en réfléchissant une demie seconde comment veux tu que l’équipe par exemple 3 se match avec l'equipe 5 si elle a été éliminé au premier tour
tu a 9 équipes tu a donc 9*(9-1) couple soit 72 possibilités
il te suffit de les répartir dans tes colonnes
pour constituer tes duels

Sub test()
equip = Array(1, 2, 3, 4, 5, 6, 7, 8, 9)
puissance = 9 * (9 - 1)
Set dico = CreateObject("scripting.dictionary")
Do
eq1 = Round(1 + (Rnd * 8))
re:
eq2 = Round(1 + (Rnd * 8)): If eq2 = eq1 Then GoTo re
dico(eq1 & "-" & eq2) = ""
Loop While dico.Count < puissance
End Sub

reste le problème que quand une équipe est éliminée dans un tour ,celles qui était sensé se mesurer a elle dans les prochains tour walouh !!!!!
et pour peu que ce duel qui n'aura pas lieu est la première apparition dans ce jeux de l’équipe programmée pour se battre contre l’équipe qui a été éliminée et ben je te le donne dans le mille "ELLE NE FERA PAS DU TOUT CE JEU " et toute les équipes dans les prochains jeux prévues contre l’équipe qui est sorti ne joueront pas se tour ou jeux et peu être même plus du tout

je comprends que tu soit a bout c'est le serpent qui se mord la queue ,un casse tète chinois, du pédalage dans le vide
j’espère t'avoir un peu éclairci les idées

 

[Douvid]

Bonjour,

Merci de ta réponse rapide.

Une équipe sortante à chaque tour ne veut néanmoins pas dire qu'elle est éliminée du tournoi, mais qu'elle ne joue pas pour ce tour précis. J'ai trouvé la combinaison pour que sur 9 tours, toutes les équipes se rencontrent une fois, avec à chaque tour une équipe différente sortante. Je ne trouve juste pas désormais la combinaison pour que chaque équipe joue le plus de jeux possible et que ce soit équitable entre les équipes. De toute façon, le tournoi compte 9 équipes, et sur chaque tour 8 équipes peuvent s'affronter en duel, soient 4 rencontres. 4 rencontres possibles à chaque tour (9 tours), ce qui donne 4x9 = 36 rencontres à placer sur la totalité du tournoi. Or, il y'a 8 jeux "duels", sur lesquels :
- Soit 4 rencontres doivent se faire, autrement dit chaque équipe ne fera pas 1 jeu du tournoi : 8 jeux x 4 rencontres possibles = 32 possibilités, donc 4 duels qui ne peuvent pas se faire (36 rencontres - 32 possibilités) et donc forcément 8 équipes ne joueront pas 1 jeu
- Soit 5 rencontres par jeu, autrement dit il faut rajouter un tour car 5 rencontres ne peuvent pas se faire en simultané (seulement 9 équipes) : 8 jeux x 5 rencontes = 40 possibilités, donc 4 rencontres qui se font 2x, sur des jeux différents pour que chaque équipe ait fait chaque jeu

Et je cherche un programme qui me permette, dans ces 2 cas, de créer le tableau de rencontres pour que chaque équipe se rencontre et joue soit tous les jeux (10 tours), soit ne joue pas 1 jeu (9 tours). Ce n'est pas facile à exprimer à l'écrit je dois dire...

 

[Dranreb]

Bonjour.
Comment feriez vous l'algorithme d'une procédure qui aurait pour tâche de ne fixer qu'un seul numéro d'équipe dans un des postes du tableau résultant recherché, sachant que vous auriez à votre disposition un moyen d'en pêcher un au hasard, et toutes facilités pour vérifier toutes conditions nécessaires à ce qu'il soit retenu ?

Édition: Tous les problèmes de tirages aléatoires pour rencontres de toutes sortes se ramènent à cette question. Mais ça débouche toujours sur un processus dont la durée est grosso modo proportionnelle à la factorielle d'une grandeur aléatoire normalement distribuée. Ce qui veut dire qu'il trouve en pratique assez souvent une solution en un temps raisonnable si on sait qu'elle existe, c'est à dire si les conditions ne sont pas trop contraignantes. Il y a alors typiquement la même très faible probabilité pour qu'il ne la trouve qu'en quelques microsecondes ou au bout de 300 millions d'années. Sachant que si cette solution n'existe pas c'est forcément la durée la plus longue qui serait nécessaire à le déterminer.
À cause de ça je n'aime pas m'attaquer à ce genre de problème. Je préfèrerais que vous preniez la responsabilité des contraintes, quitte à ce que je vous fournisse seulement les outils pour l'écrire à vos risques.

 

[Douvid]

Bonjour,

Je comprends. Merci de votre réponse. Il y'a, c'est certain, une réponse possible. Mais combien de temps faut-il pour la trouver c'est autre chose...

J'ai finalement fait autrement, le tournoi est demain et je ne pouvais pas attendre. J'ai rajouté un tour, et j'ai réussi à ce que chaque équipe se rencontre sur chaque jeu, même si il y'a des doublons de duels et des équipes qui font 2x les jeux. Ce n'est pas grave, le rapport entre la solution trouvée et les efforts faits me convient !

Merci quand même pour vos réponses et votre volonté de m'aider !

David