Problème calcul combinatoire

Bonjour,
Avec un nombre pair, de toute façon, ça n'est pas possible que chacun voie tout le monde et ne revoie jamais 2 fois la même personne.
Car si tu considères uniquement le type n°1, à chaque réunion, il va rencontrer 2 personnes (dans le triplet, il y a lui + 2 autres). Donc, si au fil des réunions, il rencontre les n° 2 et 3, puis 4 et 5, ... puis 58 et 59, à la fin, qui peut-on mettre pour compléter le triplet pour lui faire rencontrer le dernier ? Il faudra forcément que ce soit quelqu'un qu'il ait déjà vu.

Salut !

Soit n un entier
Si les personnes se rencontraient à 2 il est clair qu'on aurait 2 parmi n rencontres en vérifiant le fait que 2 personnes ne se rencontrent jamais. Maintenant comme elles se rencontrent à 3 et que parmi 3 personnes il existe 3 rencontres par groupe de 2 (12,13 et 23) alors on a 1/3*(2 parmi n) rencontres possibles.

Pour n= 9 : 1/3*(2parmi9)=1/3*9*8/2 = 12...c'est bon signe

- D'ailleurs tu peux même trouver le nombre de p-uplets à faire (imaginons que tu veuilles faire autre chose que des triplets) ça sera (2 parmi n)/(2 parmi p) lorsque c'est un entier...

- Pour 60 personnes on trouve 590 triplets....tu vas bien t'amuser à les faire à la main

Il est dit que 2 personnes ne peuvent jamais se rencontrer 2 fois et c'est ça qui est important, d'où l'idée de faire intervenir des rencontres à 2 sans que 2 personnes se rencontrent 2 fois (là la réponse est très simple). Mais il est dit que les rencontres se font 3 par 3 sous la même contrainte, donc il suffit d'enlever toutes les rencontres "inter-triplets" d'où le 1/3.
Par exemple dans ce modèle on impose pr commencer le triplet (1,2,3) qui sera donc issu des rencontres (1,2) (1,3) (2,3). On est sûr que par exemple, on n'aura jamais le triplet (1,2,x) car celui ci serait issu des rencontres (1,2) (1,x) (2,x) ce qui est impossible car le (1,2) à déjà été "pris" par le (1,2,3)...J'espère que tu vois le raisonnement, je n'ai pas vraiment de justifications mathématique là dessus, car mis à part au lycée je n'ai jamais fait de dénombrement.

La solution que je donne n'est valable que si le problème possède effectivement une solution la formule ne veut rien dire lorsqu'il n'y a pas de solutions, il est clair que n doit être impair. Malheureusement cette technique ne donne pas d'algorithme pour trouver les triplets...on pourrait penser commencer par les paires et fermer des cycles, mais la manière de faire peut amener à une contradiction...Peut être qu'en les écrivant et en barrant des cycles les plus "disjoints" on arrive à la solution...

12 13 14 15 16 17 18 19
23 24 25 26 27 28 29
34 35 36 37 38 39
45 46 47 48 49
56 57 58 59
67 68 69
78 79
89

Genre tu barres le premier, celui d'en dessous, et le troisième qui lui est associé (en rouge et en remplace le tout par 123). Ensuite tu passes à la ligne du 4, tu barres le premier celui d'en dessous et le 3e qui leur est associé, et idem avec la ligne du 7 : ainsi on a fait un tour de tous les nombres entre 1 et 9 en ne les utilisant qu'une seule fois chacun. Ensuite, je pense qu'il suffit de prendre un cycle au hasard (1,4,7) qui est donné par (14 17 47) le barrer et faire en sorte que les autres cycles à barrer ne contiennent pas (1,4,7)..une fois qu'on épuisé les nombres jusqu'à neuf, on recommence la même chose jusqu'à ce qu'il ne reste plus rien...bon enfin c'est très intuitif pour le moment mais je sens que ça va marcher...Quant à mettre ça sur un ordi, je ne suis pas calé en informatique, donc à voir avec quelqu'un de compétent.
Le bon côté de cet algo est qu'on est sûr que 2 personnes ne se rencontreront jamais 2 fois, mais ça ne garantie pas qu'on tombe sur une solution car la manière de procéder va déterminer si le résultat sera bon...à méditer...
En procedant ainsi avec 9 éléments, j'arrive à cela :
12 13 14 15 16 17 18 19
23 24 25 26 27 28 29
34 35 36 37 38 39
45 46 47 48 49
56 57 58 59
67 68 69
78 79
89
Je ne met pas toutes les couleurs pr ne pas surcharger...mais ça marche Maintenant il va falloir le faire pour 3*580 paires.... (dans ton cas les cycles à fermer feront une longueur de 580 éléments, rien que ça, mais tu arriveras à une solution correcte sans trop de "casser le tête", c'est déjà ça)

Je viens de réfléchir encore au problème, je pense avoir une idée pour le programmer sur le pc malgré mes faibles connaissances en info. Je pensais parcourir la liste des paires, de repérer les triplets dépendants de les mémoriser en retirant de la liste les 3 paires associées.. il faudra ajouter qques tests ne serait-ce que pour faire en sorte de n'utiliser qu'une et une seule fois chaque nombre pour tout parcours de 580/3 éléments...
PS : Ca ne marchera que si le n est un multiple de 3 impair car dans ma méthode on voit que ça fonctionne par "paquet" de 3...dans ton cas, il serait bon de prendre 63 ou 57 et non 60...
Je te tiens au courant, je regarde ça demain, car je n'ai pas beaucoup de travail en ce moment là je vais dormir

PS : juste par curiolité : pourquoi as tu besoin de cela ? (si c'est pas indiscret)

Bonjour,
Je viens de lire le message.
Est ce toujours d'actualité ou est ce devenu obsolète de définir la liste des triplets?
Merci de me répondre SVP.
A bientôt

Oui Gaby, ce problème a été compris et résolu


On envisage d'organiser des rencontres par triplets (par groupes de 3 personnes) et cela en partant d'une masse d'environ 60 personnes
Chaque personne pourra bien entendu participer (avec succession chronologique forcément) à autant de rencontres qu'elle voudra mais à condition d'avoir à chaque fois, en face d'elle, 2 nouveaux visages.

Combien de triplets peuvent avoir lieu au même moment?
Réponse 60:3 = 20
On voit que si le nombre de 60 avait été différent, il y aurait eu une ou deux personnes condamnées à faire tapisserie

A combien de rencontres, chaque participant peut-il participer?

Il me semble que dans ces conditions, il n'est plus besoin de calcul combinatoire
Le problème est simple: Chacun a 59 personnes à rencontrer par groupe de 2, entièrement nouveaux. Ca fait donc 29 rencontres et il y aura une soixantième personne qu'il ne pourra pas rencontrer.

Comme cela vaut pour chacun des 60 participants, on peut en déduire qu'il y aura 60 x 29 soit 1740 triplets

En fait, étant donné que 60 se divise bien par 3, personne ne fera concrètement tapisserie mais il y aura bien pour chaque participant, une soixantième personne qu'elle ne pourra jamais rencontrer.

Or, chaque fois qu'une personne (ou un pays) résout un de ses besoin de bi-rencontre, ses deux partenaires résolvent, au cours de cette même réunion, un de leurs propres besoins.
Il faut donc diviser le chiffre de 1740 par 3 et ça fait 580 rencontres pour 60 pays



Vérification

Dans le cas de 9 pays (ou personnes ou groupes de personnes d'un même pays) l'application de la formule donne :
8 personnes à rencontrer pour chacun
soit 4 paires de personnes à rencontrer pour chacun, soit 4 réunions pour chacun.
Or 9 personnes ont ce même besoin
Ca ferait donc 4x9 = 36 réunions
Mais il faut diviser par 3 car chaque fois que l'un résout un besoin de rencontrer 2 nouvelles personnes (ou pays) les deux personnes (ou pays) rencontrées en résolvent une aussi.
36:3= 12

Merci Gaby,

Curieux ce problème tout de même, à mes yeux en tous cas.
On réfléchit un peu et, nonobstant toute formation au calcul combinatoire, on découvre la solution, plutôt simple d'ailleurs.

Mais là où ça coince, c'est quand on demande d'établir un des listings possibles de ces centaines de réunions: Quel pays rencontrera quels autres pays...

Je découvre donc que si l'on est très fort en math on peut parvenir à calculer combien il y a de combinaisons dans tel ou tel problème mais on reste banalement impuissant à établir une liste nomminative. On ne peut la faire que manuellement et très laborieusement.


Il nous faut absolument l'aide de machines (déjà pour calculer les puissances ou les factorielles élevées) pour étabir les fastidieuses mais indispensables listes.

Dans mon exemple, comme il faut organiser des centaines de réunions entre ambassadeurs, l'établissement d'une liste (d'une des listes possibles) est indispensable.

Et là il faut une machine et un algorithme ad hoc. Ouille, les gros "ennuis" commencent là. En tous cas pour moi !


A te lire, on dirait que tu saurais proposer un algorithme pour qu'un PC nous ponde une des listes possibles.
Si c'est bien le cas, tu peux nous montrer un peu par quel cheminement tu passerais?





Poussons plus loin l'application pratique.
On va voir que ça se complique


Comme il s'agirait de faire se rencontrer des ambassadeurs par triplets et sur plusieurs jours, (Posons qu'il n'y ait de la place-temps pour n'organiser que 100 réunions-triplet par jour) il faut considérer que leurs emplois du temps ne leur permettront pas forcément de répondre présent au moment déterminé par le listing.
Il faudrait donc pouvoir disposer réellement de toutes les combinaisons de listes possibles et -chaque ambassadeur ayant posé ses dates disponibles- confronter électroniquement, ces listes aux dates disponibles pour trouver la meilleure satisfaction globale (ou le plus petit désagrément)

Tu saurais flirter avec ce genre de problème?

en fait pour répondre à ce genre de rproblème, il y a plusieurs solutions. Ce dont tu parles ressemble à un emploi du temps, en cherchant bien on doit pouvoir trouver des produits sur le net.
Si ces produits coutent ou ne suffisent pas il faut un developpement particulier, soit sur des produits du marché (ILOG ou autres) soit sur des produits maison (mais pas moins proffessionnel juste adapté à un problème et réutilisables).
En fait la PPC comme son nom l'indique est la programmation par contrainte. En clair l'ensemble de réunions demandées ont un certain nombre de participant qui ont un certain nombre de contraintes. Le problème est par nature combinatoire avec une ou plusieurs combinaisons possibles comme solutions.
Pour résoudre il faut bien comprendre le problème et savoir le décrire : le spécifier et donner toutes ses règles de manière non ambigue, les math aident à la description sans que ce soit une obligation
Par la suite, la description permet de déduire un modèle : modèle de données, relations entres les données, solutions à obtenirs.
La suite est de mettre en place un algorithme générant des combinaisons et de vérifier si chaque combinaison est une solution via les contraintes ou règles (relations entre les données) exprimées (d'ou la nécessité de bien décrire le problème et ses contraintes, ces dernières portant sur les données).
Dans la pratique, l'algortihme "aide" à la recherche de solutions, l'ensemble des combinaisons est représentée par un graphe, le but étant de limiter ce graphe aux combinaisons qui sont des solutions. C'est tout ce que fait la PPC.
Voila, désolé si cela peut paraitre un peu obscur, il faut retenir que poser le problème est la clé du succès, modéliser et résoudre devient plus aisé par la suite.
C'est quand même tout un métier, mais j'espère y avoir un peu répondu.
L'exercice vaut le coup d'être tenté.

Je ne suis pas sur de te suivre, si c'est de l'ironie ou pas.
Juste que donner un algorithme en quelques secondes voir quelques minutes n'est pas immédiat.
Je ne donne que quelques pistes pour indiquer qu'il existe des outils : EDT sur le NET est un logiciel d'emploi du temps : si tu recherche tu verras que cela existe depuis peu pourtant l'éducation nationnale en a grand besoin et ce n'est pas immédiat à utiliser. ILOG produit un logiciel générique pour traiter des contraintes : c'est principalement ton problème.
Je n'ai pas dit qu'il y a une solution simple, j'ai dit qu'il existe des outils pour traiter les problèmes combinatoire et qu'il faut les mettre en oeuvre et que cela fonctionne vraiment.
Pour résoudre sérieusement, il n'y a pas 4 lignes de code à pondre.
Je ne parle pas de bidouiller mais de donner une solution qui soit réelle, consistante, evolutive et permettre de prendre d'autres contraintes : aujourd'hui des réunions, demain des horaires adaptés, plus tard des contraintes de gestion de salles de réunion ou de langues communes etc...
Le conduite à tenir est :spécifier, modèliser, developper.
C'est un vrai travail.
Le but est de construire l'ensemble des solutions et de les filtrer suivant des règles (grosso modo) : réduire le domaine suivant des règles.
Exemple: tu construit toutes tes combinaisons, par exemple: (1,1,1) ( 1,1,2) etc... sans préjuger donc une liste de (A,B,C).
Premiere contrainte : tous les participants à une réunion sont "forcement" différent.
Cela va sans dire mais cela va mieux en le disant. Donc cette regle se traduit par A different de B, B different de C, A different de C. Ton algo va donc enlever tout ce qui ne verifie pas cette regle (première reduction de domaine).
Seconde contrainte : (1,2,3) est equivalent à (2,3,1) etc. le but est de virer les symetries , seconde reduction de domaine
Etc....
A la fin, chaque contrainte permet de reduire ta liste et te donne la liste finale ou les listes finales.
Le problème est de bien ecrire les contraintes et de les appliquer, c'est de la PPC, il faut un moteur de contrainte (ILOG ou autre) et ecrire/developper les contraintes.
Par la suite c'est le moteur qui sait gerer les impasses et est capable de revenir en arrière faire d'autres choix, prendre d'autres décisions. Tout cela ne peut êtyre decrit dans une routine C, C++ ou autre, il faut un logiciel capable de traiter , de faire des combinaisons et de le remmettre en cause le cas echeant.
Voila pourquoi il n'est pas possible de donner un algorithme en quelques lignes.
Pour finir, si tu recherche PPC sur le NET et que tu y trouves un cours comme moi il y a quelques annees tu apprendra et comprendra qu'il y a une autre logique pour résoudre les problème combinatoire. La PPC en est une et fait partie des domaines de l'IA, d'aide à la décision. (meme pour ton problème qui parait simple mais qui n'est pas immediat à resoudre) C'est comme le probleme classique parmis les classiques du voyageur de commerce qui doit optimiser sa tournée ou refaire un planning des qu'un prof est absent etc...
Si quelqu'un te propose un logiciel ecrit sur un coin de table en 10 minutes et qui resout ton probleme, n'hesites pas.

Oui Gaby, tu évoques le problème du planing des profs que les directeurs d'école doivent réaliser.

Punaise, ça m'a toujours semblé être un problème diabolique (sans parler des perturbations créées par les absences ou autres aléas de parcours)
Et je me suis souvent demandé quelle méthode les dirlos utilisaient.

De nos jours, je n'ai plus de doute que des spécialistes dans ton genre ont su leur proposer des logiciels capables de résoudre ces casse-têtes mais en procédant, là encore, par scannage de toutes les solutions brutes et par élimination des mauvaises soluces, non par création directe et ab nihilo des bonnes soluces.
J'imagine que les dirlos doivent vous bénir ;°)

Bien enrtendu. On ne part pas de TOUTES les solutions imaginables mais seulement de Toutes les éligibles en ce problème.
C'est sur cette cohorte présélectionnée (établie avec les techniques de dénombrement basiques) qu'on mène la vérification des contraintes pour en extraire les élus. Pour détecter un champion d'échec on ne va pas chercher parmi ceux qui n'y jouent jamais.
L'adresse du solutionneur se manifeste un peu dans l'élaboration de cette cohorte de base mais surtout dans l'élaboration du système PPC qui va s'appliquer sur cette cohorte.
Et dans ce travail (où il faut une belle intelligence) il faut en effet concevoir de devoir parfois revenir en arrière en cas d'impasse ou de bogue du système de triage.

Dans le fond, c'est probablement à peu près ce genre de démarche qu'entreprennent les gars de Microsoft pour protéger leurs programmes. Mais ils ont beau gamberger, ils ne parviennent pas à prévoir toutes les failles possibles pendant que des hackers les trouvent.