Fonction de brassage

[MoodCode]

Bonjour à tous,

J'ai pas mal hésité à venir sur ce forum précisément, mais il se pourrait que les mathématiques soient la clef de mon problème.
Je suis développeur et je dois réaliser une fonction permettant d'organiser des "speed meeting", comme des speed dating mais pour les entreprises.

Je vais donc avoir "n" participants, regroupés sur "n" tables sur "n" tours.
Chaque participant doit pouvoir s'exprimer "n" minutes.

Le principe est de faire en sorte qu'aucune personne ne rencontre deux fois la même personne, donc de proposer des tables ayant des combinaisons uniques durant toute la session.
Sachant que des personnes (les retardataires) peuvent aussi s'intégrer en cours de rencontre.
L'absence d'une personne n'est pas un problème (une chaise de moins laissant plus de temps aux autres participants pour s'exprimer).

Il y a tout de même des limites :
- 150 personnes max
- 2h30 de durée max
- 10 par table max

Avec un algo c'est, pour moi, un vrai casse tête, pensez-vous qu'il y ait une solution mathématique que je pourrais alors intégrer dans ma fonction ?

Merci pour vos retours éventuels.
-----

[albanxiii]

Bonjour et bienvenue sur le forum,

Quelques précisions sur votre problème...

Je vais donc avoir "n" participants, regroupés sur "n" tables sur "n" tours.
Chaque participant doit pouvoir s'exprimer "n" minutes.

Est-ce le même n à chaque fois ou bien est-ce que ce sont des n différents ? (par exemple est-ce qu'on peut avoir 30 participants, 8 tables, 3 tours, 5 min ?)

Sachant que des personnes (les retardataires) peuvent aussi s'intégrer en cours de rencontre.

A mon avis, ça complique beaucoup le problème. Peut-être dans un premier temps faire comme si le nombre de participants était fixe et regarder ce qu'il faut changer s'il ne l'est plus.

[gg0]

Bonjour.

Une méthode simple est de constituer un nombre pair de groupes de p personnes (p<=10), puis au premier tout, 1 rencontre 2, 3 rencontre 4, etc. Les tours suivants se font en conservant les tables et faisant une permutation circulaire sur 2,3,4, ...2n.
par exemple avec 6 groupes :
Premier tour :
1 3 5
2 4 6
deuxième tour
1 5 6
3 2 4
troisième tour
1 6 4
5 3 2
etc.

La permutation circulaire fait que 1 ne rencontre jamais les mêmes sur les 5 tours, et que les décalages de 2 sur 5 groupes donnent aussi les 5 tables différentes possibles.

Cordialement.

[MoodCode]

Bonjour Albanxiii et merci pour votre réponse.

Oui, "n" est différent en effet. Il peut y avoir par exemple 80 personnes d'inscrites, ou même un nombre impair d'ailleurs, nous ne contrôlons que le maximum d'inscriptions possible pour chaque évènement.

Concernant les ajouts de personnes, si je trouve le moyen d'effectuer le brassage avec toutes ces variables, je pourrais relancer la fonction à la volée, pour le logiciel ce ne sera pas un problème.
J'ai donc pensé que pour le raisonnement il valait mieux le prendre en compte dès le début, mais ce n'était qu'un apriori.

[A voir en vidéo sur Futura]

[MoodCode]

Bonjour ggo et merci pour votre réponse.

J'ai du mal à vous suivre. Si je me fie à votre tour 1 et 2 on voit que la personne 1 rencontre 2 fois la personne 3 par exemple, qu'est-ce qui m'échappe ?

J'ai besoin de :
Tour 1
table 1
p1, p2 p3 p4 etc. jusqu'à (par exemple) p10

Tour 1
table 2
p11, p12 etc.

Etc.

Et que pour les tours suivants (T2, T3 etc.), après le brassage, que p1 ne croisent plus jamais les p déjà rencontrés.

[Biname]

Salut,
https://fr.wikipedia.org/wiki/Discus...ser_un_tournoi
Biname

[gg0]

Heu ... la personne 1 rencontre la 2 au premier tour, la 3 au second tour, la 5 au suivant, ... Mais je pensais plutôt le groupe 1 rencontre le 2 au premier tour, le 3 au second tour, le 5 au suivant, ...
En fait j'avais compris que tu voulais faire se rencontrer des groupes; finalement, ce n'est pas ça.

[MoodCode]

Je vois que ça ne semble pas simple non plus à des esprits rompus aux mathématiques, c'est donc peut-être plus un problème d'algorithmie finalement.

[MissJenny]

si j'ai bien compris on a n=km personnes qu'on veut regrouper en m tables de k personnes, plusieurs fois et de telle sorte que pour tous i,j les personnes i et j soient une fois et une seule à la même table. Ce problème n'a pas toujours de solutions.

Tu peux le voir facilement en prenant n=6,m=2,k=3. Au premier tour tu as les tables {1,2,3} et {4,5,6}. Au deuxième tour 1 doit avoir 2 compagnons de tablée pris parmi {4,5,6}, mais aucune des tables {1,4,5}, {1,5,6} ou {1,4,6} ne convient.

[jacknicklaus]

à première vue, pas de solution si plus de chaises par table que de tables.

problème intéressant et pas trivial !

[MoodCode]

@MissJenny
Voilà c'est ça, minimum 20 personnes, en dessous nous faisons des duos.
En général nous comptons une vingtaine de personnes et sur certains gros événements nous pouvons aller jusqu'à 100 / 150 personnes.

Le nombre de personnes assisent à une même table et le nombre de tables peuvent être imposés par la logique si nécessaire.
Une personne prend la parole en 1 et 4 minutes mais c'est là aussi imposé par la durée de l'événement qui ne doit pas dépasser 2h30.

Je suis en train de me demander si une IA ne serait pas la parfaire candidate pour ce genre de sport... Elle produit des millions de résultats et ne conserve que ceux étant juste. il serait alors facile de produite n tours de 10 tables.
Va falloir que je me forme à Python je sens.

@jacknicklaus Oui pas simple Nous pouvons écarter tout ce qui est logiquement bloquant.

[Merlin95]

Et si tu fais simplement des tirages au hasard et tu nenprends pas en compte les configurations non valides ?

[MoodCode]

Oui effectivement je tends vers ça. Je parlais d'une IA pour sa capacité de traitement mais en fonction du % de chances de trouver un résultat correcte je peux le tenter en php pourquoi pas. Ça mûrit gentiment.
Bon, en tout cas merci pour vos interventions à tous, vos réflexions m'ont bien aidé.

[Biname]

Salut,

Un participant rencontre des paires de participants, il y aura donc un nombre impaire de participants, lui + n paires des participants
Pour remplir les tables de trois, le nombre de participants doit être un multiple de 3

soit P le nombre de participants, p = 3 * (2n + 1) pour n = 0 à k, il y a (p - 1)/2 tours
Nombre de participants : p 3, 9, 15, 21, 27, 33,

Trois participants est trivial 1 2 3

Essayons avec 9 participants a, b, c, d, e, f, g, h, i
il faudra (9 - 1)/2 tours

1er tour    2e tour     3e tour         OK                      manquent          4e tour

a b c       d b i       g b f           a : b c  e i  h f       a d  et  a g      a d g
d e f       g e c       a e i           b : a c  d i  g f       b e  et  b h      b e h
g h i       a h f       d h c           c : a b  g e  d h       c f  et  c i      c f i   ha ha ha aide du destin

2e et 3e tour, la colonne 2 est immobile, la colonne 1 'monte' et la colonne 3 descend 
4e tour Xij >> Xji 

on complète en écrivant le premier tableau Xij >> Xji

Avec 15 participants ? On a 7 tours, 4 rotations et la transposée ... manque un tour .. non ?

Biname

[MoodCode]

@Biname
Voilà, en venant ici j'avais l'espoir de trouver une sorte de formule ou de séquence dans le genre en effet.

Qu'entends tu par "Un participant rencontre des paires de participants". C'est un postulat ?

En suite tu dis "P = nombre de participants", P = p ?
Et du coup je ne comprends pas cette formule : "p = 3 * (2n + 1)"

Le nombre de tour n'est pas imposé dans la mesure ou tout le monde ne doit pas obligatoirement rencontrer tout le monde. Certaines personnes ne rencontrent pas certaines autres, ça n'est pas un souci.
La seule contrainte à ce niveau là c'est qu'une personne ne rencontre jamais une autre personne plus d'une fois (ça tu le prends bien en compte).
Ce qui signifie que "(p - 1)/2 tours", le 2 serait en fait une variable choisie par l'organisateur avant sa rencontre (si je t'ai bien suivi), mais alors est-ce que ton raisonnement marche toujours ?

Merci

[Biname]

Salut,

@Biname
Qu'entends tu par "Un participant rencontre des paires de participants". C'est un postulat ?

Il y a trois personnes à chaque table, donc une personne voit défiler les participants deux par deux : des paires, toutes ces paires sont distinctes, une même personne n'apparaît jamais dans deux de ces paires, sans quoi la première personne verra défiler deux fois la personne commune à deux de ces paires.

En suite tu dis "P = nombre de participants", P = p ?
Et du coup je ne comprends pas cette formule : "p = 3 * (2n + 1)"

Oui, P=p et du coup tu comprends mieux. P = le nombre de participants

Le nombre de tour n'est pas imposé dans la mesure ou tout le monde ne doit pas obligatoirement rencontrer tout le monde. Certaines personnes ne rencontrent pas certaines autres, ça n'est pas un souci.

La solution triviale 'personne ne rencontre personne' ne convient pas, je présume.
Dans l'exemple à 9 personnes ci-dessus, tout le monde rencontre tout le monde une seule fois, c'est possible si on respecte la règle concernant le nombre de participants P = 6 n + 3 = 3 * (2n + 1) . Permis : 3, 9, 15, 21, 27, 33, 39, 45, 51, 57, ... participants, on complète avec des 'morts'(max 5) ce qui mènera à des tables à 3 morts, à 1 toute seule et à deux ... au pire.

La seule contrainte à ce niveau là c'est qu'une personne ne rencontre jamais une autre personne plus d'une fois (ça tu le prends bien en compte).

Alors, c'est simple, tu limites le nombre de tour à P/3 et tu roules les colonnes comme dans l'exemple, le nombre de lignes doit être paire, mais ceci sera toujours vrai si on respecte la règle du nombre de participants(on peut remplir avec des 'morts' ou des 'désistés').
Dans ce cas, tu perds (P - 1)/2 - P/3 = P/2 - 1/2 - P/3 = (P - 3)/6 tours, ce qui signifie que chaque participant ne verra pas 2 * (P - 3)/6 = (P - 3)/3 participants,
soit environ 1/3 des participants.

Sauf erreur facile à corriger

Ce qui signifie que "(p - 1)/2 tours", le 2 serait en fait une variable choisie par l'organisateur avant sa rencontre (si je t'ai bien suivi), mais alors est-ce que ton raisonnement marche toujours ?

Non ! (P -1)/2 est le nombre de tours qui permet à tout le monde de rencontrer tout le mode une seule fois.

Biname

[Biname]

Salut,
Si tout le monde ne doit pas nécessairement voir tout le monde, un fonctionnement sur des tables numérotées de 1 à K = P/3, est plus simple (P = nombre de participants = 3 + 6*N ou 3,9,15,21,27, ...).

A chaque table numérotées de 1 à K, il y a 3 personnes
- une ne se déplace jamais (Personne de type 0)
- une autre va toujours vers la table T+1 (personne de type +1)
- l'autre va toujours vers la gauche T-1 (personne de type -1)

Lorsqu'une personne arrive en bout de table en K, son prochain mouvement sera vers la table 1
Lorsqu'une personne arrive en bout de table en 1, son prochain mouvement sera vers la table K
Les unes(+1) tournent dans un sens les autres(-1) dans l'autre.

Si les tables sont placées en cercle, en boucle(carrée éventuellement) c'est encore plus simple ...

Ainsi, après P/3 tours, chaque participant aura vu 2/3 des autres participants. Les personnes de type 0 ne se seront pas rencontrées.

Biname

[Biname]

Salut,
Etait Faux

Biname

[MissJenny]

Je suis en train de me demander si une IA ne serait pas la parfaire candidate pour ce genre de sport... Elle produit des millions de résultats et ne conserve que ceux étant juste. il serait alors facile de produite n tours de 10 tables.

as-tu une idée du nombre de façons de répartir 100 personnes en 10 groupes? Tu es loin du compte quand tu parles de millions de possibilités.

[jacknicklaus]

as-tu une idée du nombre de façons de répartir 100 personnes en 10 groupes? Tu es loin du compte quand tu parles de millions de possibilités.

Un nombre à 93 chiffres...

[MoodCode]

@MissJenny Aucune idée non, mais je ne cherche pas à trouver toutes les combinaisons...

Il me faudrait un grand nombre de possibilités "justes" pour pouvoir en trouver quelques unes rapidement (aléatoirement).
Si l'algo ou l'IA trouve un réponse juste je la sélectionne, sinon je passe à la suivante.
D'autant que je n'ai pas toute la combinaisons à tester mais un simple couple puisque si un couple est faux la combinaisons (la table donc) l'est aussi.

Sauvegarder la liste des duo déjà effectués ne coute pas grand chose en mémoire ou un calcul. Idem pour la comparaison.

@Biname je n'ai pas encore pu prendre le temps de me pencher sur ta solution.

@jacknicklaus
Parfait ! J'ai donc de très grandes chances de tomber rapidement sur des combinaisons justes.

[MissJenny]

Parfait ! J'ai donc de très grandes chances de tomber rapidement sur des combinaisons justes.

intuitivement je dirais qu'il y a très peu de combinaisons correctes, et je pense que tu n'as aucune chance d'y arriver en testant des répartitions au hasard.

[jacknicklaus]

intuitivement je dirais qu'il y a très peu de combinaisons correctes, et je pense que tu n'as aucune chance d'y arriver en testant des répartitions au hasard.

+1
10 caractères

[MoodCode]

D'accord, donc il faut une "mécanique" mathématique ?
Un "décalage" comme le propose @biname ?
Mais nous devons prendre en compte les contraintes physiques, par exemple le nombre de tables. Peu de lieux peuvent nous proposer plus de 10 tables de 10 personnes (et c'est déjà un bel exploit).
@biname tu trouves le nombre de tables en /3 le nombre de personnes mais ta proposition fonctionne-t-elle aussi avec un /10 ? Je ne peux pas faire une tournante de 33 tables, c'est impossible...

[Biname]

Salut,
@MonCode
Ce principe fonctionne pour un nombre impair de tables de trois participants, chacun rencontrera les deux tiers des participants. Il ne rencontrera jamais les membres de sa ligne.

Pour 3, 9, 27, 81, ... tables de trois personnes, il y a une solution parfaite : tout le monde rencontre tout le monde une seule fois.

Pour trois tables de trois participants

 1er Tour   (L pour ligne et T pour table, participant N° 101, N°102, ... on commence à N° 101)
    ! T1  ! T2  ! T3
-----------------------
L1  ! 101 ! 102 ! 103
L2  ! 104 ! 105 ! 106
L3  ! 107 ! 108 ! 109
-----------------------

 2eme Tour (Rot L1> et L3< With Carry)
103  101  102
104  105  106
108  109  107

 3eme Tour (Rot L1> et L3< With Carry>
102  103  101
104  105  106
109  107  108

Les participants des lignes ne se rencontrant pas, il suffit alors de les rassembler à une
même table au quatrième tour

  4eme Tour
101  104  107
102  105  108
103  106  109

Et tout le monde a vu tout le monde une seule fois.

Ce serait bien que tu nous fasses un croquis des tables et des rotations pour nous montrer que tu as compris.

Biname