Discussion :

[Kijer]

Bonjour,

Développeur PHP dans de la création classique de sites webs, j'ai pour "défi" de réaliser un petit programme permettant pour un nombre donnée de participants, de les répartir sur X tables (le meuble) et x personnes par table. Quand chaque participant s'est présenté, tout le monde change de table et rencontre de nouvelles personnes. Le but étant dans un temps donné de voir le maximum de personnes sans croiser une même personne.

Ayant un parcours autodidacte, je n'ai jamais été confronté à faire de l'algorithmie, je ne sais donc même pas par où commencer et comment concevoir ce truc, des pistes ?

Merci

[marcallag]

Bonjour,

Déjà tu devrais te poser la question de savoir à quoi concrètement ton programme va te servir. Comment tu vas l'utiliser ?

[Dumbeldor]

Salut kijer,

L'algo c'est pas quelques choses de compliquer en soit.
Si tu es logique tu comprendras vite comment faire.
Je te conseil vivement d'aller voir du côté des cours -> http://algo.developpez.com/cours/
Il y a quelques trucs à savoir pour faire de l'algo après tu peux tous faire avec, et franchement c'est vraiment confortable de coder avec ton algo sous les yeux, même plus besoin de réfléchir les seuls problème que tu peux rencontrer sont des soucis de syntaxe de ton langage (Donc vraiment reposant !)

Va faire un tour sur les cours et reviens nous voir si tu as des questions.

[Deuzz]

Bonsoir

Voici juste quelques considérations mathématiques à propos du problème posé.

Les données de départ sont :

• Le nombre total de participants : X
• Le nombre de tables : Y
• Le nombre de personnes par tables : Z

Cependant seules deux de ces données peuvent être fixées car pour que chacun puisse trouver une place sur une table complète il faut respecter la règle suivante : Y x Z = X
De plus pour qu'il y ait une solution il faut qu'il y ait plus de tables que de personnes par table Y > Z
(En effet si Z > Y il sera impossible de répartir les participants des premières tables sans que certains se retrouvent dès le deuxième tour)
A chaque tour les participants se retrouvent sur une table avec des personnes inconnues.
Chaque personne peut donc rencontrer (X - 1) personnes au rythme de (Y - 1) rencontres par tour.
Le nombre maximum de tours est donc T = E ((X-1)/(Y-1))
(Rappel : E(X) est le plus grand entier inférieur ou égal à X)
Et le nombre de personnes que l'on ne pourra rencontrer est de (X - 1) modulo T
Pour qu'il y ait une solution parfaite il faut donc que T(Y-1)=X-1
(Solution parfaite : chaque participant peut rencontrer TOUS les autres sans croiser deux fois la même personne)

[Kijer]

Bonjour,

Déjà tu devrais te poser la question de savoir à quoi concrètement ton programme va te servir. Comment tu vas l'utiliser ?

Le but est de réunir des professionnels ensemble, et les faire se rencontrer en se groupant par table, le but de l'algo est de permettre de proposer un déroulement et chemin de table à respecter afin de ne pas qu'un participant retrouve sur un autre tour une même personne.

Salut kijer,

L'algo c'est pas quelques choses de compliquer en soit.
Si tu es logique tu comprendras vite comment faire.
Je te conseil vivement d'aller voir du côté des cours -> http://algo.developpez.com/cours/
Il y a quelques trucs à savoir pour faire de l'algo après tu peux tous faire avec, et franchement c'est vraiment confortable de coder avec ton algo sous les yeux, même plus besoin de réfléchir les seuls problème que tu peux rencontrer sont des soucis de syntaxe de ton langage (Donc vraiment reposant !)

Va faire un tour sur les cours et reviens nous voir si tu as des questions.

Ne connaissant que de loin le sujet, je te rejoins sur le principe de la logique, mais j'imagine que pour avancer il faut avoir une culture sur les formules, des lois, etc.. afin d'appliquer tel concept pour tel problématique. Et c'est justement là où je vais peiner :-)
Je vais regarder ton lien cependant ca me fera pas de mal.

Bonsoir

Voici juste quelques considérations mathématiques à propos du problème posé.

Les données de départ sont :

• Le nombre total de participants : X
• Le nombre de tables : Y
• Le nombre de personnes par tables : Z

Cependant seules deux de ces données peuvent être fixées car pour que chacun puisse trouver une place sur une table complète il faut respecter la règle suivante : Y x Z = X
De plus pour qu'il y ait une solution il faut qu'il y ait plus de tables que de personnes par table Y > Z
(En effet si Z > Y il sera impossible de répartir les participants des premières tables sans que certains se retrouvent dès le deuxième tour)
A chaque tour les participants se retrouvent sur une table avec des personnes inconnues.
Chaque personne peut donc rencontrer (X - 1) personnes au rythme de (Y - 1) rencontres par tour.
Le nombre maximum de tours est donc T = E ((X-1)/(Y-1))
(Rappel : E(X) est le plus grand entier inférieur ou égal à X)
Et le nombre de personnes que l'on ne pourra rencontrer est de (X - 1) modulo T
Pour qu'il y ait une solution parfaite il faut donc que T(Y-1)=X-1
(Solution parfaite : chaque participant peut rencontrer TOUS les autres sans croiser deux fois la même personne)

J'étais tombé sur ce lien : http://www.matchmaking-studio.com/ou...ogistique.html car j'avais effectivement oublié une donnée : le temps. (souvent 1h30) Leurs solutions semblent calculer la solution la plus adapté pour tels données. J'en suis pas à ce niveau pour le moment ! L'idée est également de prévoir des retardataires permettant de s'incruster dans des tables sans chambouler l'ensemble de l'organisation.

Je me pose, et analyse ton pseudo-code afin de l'assimiler :-) Merci !

[tbc92]

Bonjour,
Je crois comprendre que l'objectif est de faire en sorte que chaque participant voie un maximum de personnes après X positions.
Il n'y a pas d'interdiction à ce qu'un participant recroise un autre participant qu'il a déjà croisé.

D'autre part, si je comprend bien l'énoncé, on peut imaginer une situation où on a des tables imposées avec 6 participants, il y a par exemple 40 participants, et donc on a des tables incomplètes.



Dans les différentes configurations , il y a une configuration qui est très simple à mettre en place :
On a n tables avec n places à chaque table, n² participants, et n est un nombre premier.
En (n+1) positions, on peut faire en sorte que tous les participants se soient tous rencontrés, par un mouvement assez simple à organiser.

Quel est ce mouvement ?

[Deuzz]

On a n tables avec n places à chaque table, n² participants, et n est un nombre premier.

Je ne comprends pas le pourquoi de cette condition que tu imposes car cela nous oblige à avoir : 1, 2, 3, 5, 7 ,11, ... tables
et donc 1, 4, 9, 25, 49, 121,... participants

[tbc92]

Je n'impose rien.
Je dis simplement que dans cette configuration très particulière, il y a une succession de mouvements assez simples qui donne une solution 'parfaite'.
C'est en quelque sorte une énigme que je soumets aux personnes intéressées, sachant que cette énigme a un rapport certain avec le sujet soumis au départ, mais quasiment aucun rapport avec l'algorithmie.

[Deuzz]

Yeeepeeeeeeeee j'ai trouvé.

Et c'est vrai que c'est presque simple...Quoique...

j'avais effectivement oublié une donnée : le temps. (souvent 1h30)

C'est pas faux : si on trouve un moyen pour que 40 personnes croisent les 39 autres mais que ça prends 3h19 on pourra repasser pour l'optimisation.

Imaginons qu'une personne mette en moyenne 3 minutes pour se présenter à une table.
De plus le temps de changer de table prend lui aussi 3 minutes

On calcule le temps que mettraient toutes les rencontres pour les différentes valeurs de n (ne pas oublier que c'est un nombre premier)
à chaque fois il y a (n+1) tours qui durent (n présentations de 3 minutes) + n changements de 3 minutes

ce qui nous donne pour

• n=2 ---> (2+1)x(2 x 3) + 2 x 3 = 24 Minutes
• n=3 ---> (3+1)x(3 x 3) + 3 x 3 = 45 Minutes
• n=5 ---> (5+1)x(5 x 3) + 5 x 3 = 105 Minutes = 1h45

STOOOOOOOP Manifestement, vu les temps proposés, un Speed-meeting de n²=25 personnes semble être le maximum

J'ai défini chaque personne par son groupe (n° de la première table occupé) et sa position (n° de la seconde table occupée)

Dans le tableau qui suit, chaque rangée correspond au parcours d'un participant
Chaque colonne représente 1 tour de 5 tables.

1er Tour : chaque participant rencontre les membres de son "groupe" 2ème Tour : chaque participant rencontre les membres des autres groupes occupant la même position dans leur groupe 3ème Tour : chaque participant rencontre le membre du groupe suivant occupant la position après la sienne (P + 1) 4ème Tour : chaque participant rencontre le membre du groupe suivant occupant la position 2 unités après la sienne (P + 2) 5ème Tour : chaque participant rencontre le membre du groupe suivant occupant la position 3 unités après la sienne (P + 3) 6ème Tour : chaque participant rencontre le membre du groupe suivant occupant la position 4 unités après la sienne (P + 4) Et voilà, chacune des 25 personnes aura rencontré les 24 autres, en 6 tours, de 5 tables de 5 personnes

Sur ce... c'est pour moi l'heure d'aller au lit...

[tbc92]

Bravo, c'est exactement ce mouvement.

Je le reformule un peu différemment.
On a 5 tables de 5 places ; Les 25 places sont codées de A1 à E5 ( A1 B1 C1 D1 E1 = table 1 ; A1 A2 A3 A4 A5 = Ceux qui sont orientés dans une direction donnée, sur les 5 tables)
1ère position, chacun s'asseoit à une table.
2ème position : Tous ceux qui étaient dans l'orientation A vont à la table 1, ceux qui étaient dans l'orientation B vont à la table 2 .. etc.

Ensuite , les autres mouvements sont toujours les mêmes :
Ceux qui sont dans l'orientation A ne bougent pas.
Ceux qui sont dans l'orientation B montent d'une table et restent dans l'orientation B.
Ceux qui sont dans l'orientation C montent de 2 tables et restent dans l'orientation C.
Ceux qui sont dans l'orientation D montent de 3 tables et restent dans l'orientation D.
Ceux qui sont dans l'orientation E montent de 4 tables ( c.a.d. descendent d'une table) et restent dans l'orientation E.

Et comme on s'est limité au cas particulier où le nombre de tables est un nombre premier, ce mouvement fonctionne parfaitement. Ici, on l'a développé avec n=5 tables, mais ça marche pour tout n premier.

[sprenzah]

Bonjour,

J'ai bien conscience que ma question arrive bien tard mais j'avais utilisé le fil de cette discussion pour organiser un business dating il y a tout juste 1 an et les explications m'avaient permises de ficeler mes tours de table. Demain je reçois 40 personnes et en reprenant les formules, je n'y comprends rien, il faut dire que je ne suis pas une matheuse...
Quelqu'un pourrait-il m'aider pour l'organisation de mes tours de tables? Merci à vous

[algoreme]

Bonjour.

J'ai créé une application web qui permet d'organiser et animer les speed meetings. Elle garantit que chaque participant rencontrera chacun des autres une fois exactement quelque soit le nombre de personnes effectivement présentes.
Son nom est KUNVENI (se rencontrer en espéranto).
Voici le site vitrine : https://www.kunveni.fr/

Merci à Deuzz et tbc92 pour l'algorithme que j'ai implémenté dans mon application.

[rossmacfirdeen]

Bonjour, je lis ce fil avec grand intérêt !

J'ai cependant 2 questions :

Question 1) Il semblerait que l'utilisation de nombres premiers soit requises : pour quelle raison ? Si je veux réaliser un speed meeting avec 8 ou 9 tables par exemple, est-ce possible en suivant ce système ?
Quelle va être le pourcentage de rencontre effectif de l'ensemble des participants ?

Question 2) Si je souhaite réaliser un évènement avec par exemple 8 tables mais avec seulement 4 voir 5 personnes par table afin le tour de table ne soit pas trop long, est ce possible ? Comment dois je ventiler et/ou sélectionner les lignes dans chacun de ces groupes afin de pouvoir remplir mes 8 tables à chaque fois avec ces 4 ou 5 personnes ?


Merci pour vos éclairages !

[tbc92]

Si tu veux précisément 4 personnes par table (ou précisément 5 ... toujours le même nombre) et si tu veux que tout le monde voit tout le monde une fois et une seule, alors il y a peu de cas où ça va marcher.

Par exemple avec 20 personnes, et des tables de 4, à chaque tour, chacun rencontre 3 autres invités. Et un invité doit rencontrer 19 personnes. 19 n'est pas un multiple de 3, c'est sûr qu'il n'y a pas de solution.
Avec 28 personnes et des tables de 4, chacun doit voir 27 autres personnes, et 27 est bien un multiple de 3. Donc on a un espoir de trouver une succession de règles qui convient, sans certitude.

Avec n² personnes, et des tables de n, si n est premier, c'est magique, il y a une solution. C'est le cas simple, il y a une solution, facile à trouver et à mettre en place ou chaque paire va se rencontre une fois et une seule.
Mais si n n'est pas premier, si on a nx4 personnes et qu'on veut des tables de 4 .... chaque cas est un cas particulier, il faut explorer tous les déplacements possibles, et peut être qu'on va trouver des solutions, ou pas.

Si tu peux combiner des tables de 4 et des tables de 5, si tu acceptes un peu de 'souplesse' (certains se voient 2 fois, ou certains ne se voient pas du tout) alors c'est beaucoup plus souple, et il y a forcément des solutions plus ou moins satisfaisantes.

[rossmacfirdeen]

Merci pour cette réponse éclairante !

J'ai essayé de pousser plus loin de sujet et il s'avère que même si je pars d'un nombre premier (5tables x 5 persones x 6 tours) comme au dessus et que je souhaite réduire par exemple à 3 personnes par table

La matrice ci dessus est bien celle que je génère par algortihme <= ca c'est ok ! (pour les premiers n premiers : 3, 5 , 7 , 11 ...)

la grille est également correctement générée avec des entiers non premiers, mais je n'ai pas encore pu vérifier le % de rencontres unitaires.

Ma question est la suivante : Imaginons que je prenne les 3 premières lignes de chacun de ces groupes (5 groupes de indéxés 0 à 4, et les participants contenus dans chacun egalement)

Je prends : G0P1 (p1), G0p2 (p2),G0p3 p3) + G1P0 (p6), G1P1 (p7),G1P2 (p8) + .... + G4(px) ....

Si je pivote (pour des raisons de visualisations) les roles pour avoir les affectation par table en fonction des tours (donc avec 3 participants par table, mais bien 6 tours) : ok ils ne se croiseront pas tous .. MAIS ...

Il y a un problème spécifiquement sur le tour #2 (sur les 5 tables), seules les 2 premieres sont pourvues de participants (6 par table !!) et les table 3,4 et 5 sont vides ..

Si on analyse les informations du tableau, ca s'explique ....

Seulement => A quoi sert la répartition par groupe dans ce cas précis ? Peut t'on ventiler aleatoirement les lignes (mélanger les groupes) afin d'espérer un meilleurs tirage ? Et comment éviter cet écueil ? (mon exemple du tour #2 plus haut ....)

Merci

[tbc92]

Si tu as par exemple 6 x6 participants, avec des tables de 6,
A la 4ème position, ceux qui sont montés d'un cran à chaque étape retombent sur un même participant qu'à la première position (ceux qui sont descendus d'un cran à chaque position).

[rossmacfirdeen]

Donc si je comprends bien, il n'y a pas de possibilité de réduire les possbilités du nombre de participants ?

Visiblement, un contributeur du post Kunveni, propose un système basé sur cet algorithme, et indique qu'il lui est possible pour 5 tables de prendre en charge de 10 (5 tables à 2 personnes / 5 tours) à 25 participants

Avec à priori un système d'alimentation séquentiel (planification au fil de l'eau)

Seulement, on ne couvre pas l'ensemble des rencontres possibles ! pour rencontrer 9 personnes sur 5 tours, il faut être plus de 2 par table !

Donc soit quelque chose m'échappe ... Soit ce n'est pas possible ...

[tbc92]

Quand tu prends 5 tables à 2 personnes, et que tu fais 5 tours, il y a en tout 5x2=10 participants, et chacun croise seulement 5 autres participants, sur 9 possibles.
Avec 10 personnes et des tables de 2, je crois comprendre que ton objectif est que tout le monde rencontre tout le monde, et donc il te faut 9 tours. Il me semble que c'est assez simple à organiser, mais que la solution proposée par l'intervenant en question ne convient pas.

En fait, je n'ai rien compris à ton message qui commence ainsi : J'ai essayé de pousser plus loin de sujet
En relisant, il n'y a aucune ligne que j'arrive à comprendre.

[valentin03]

Bonjour,
Je vois que autant "Kije" que "sprenzah" parlent de plusieurs participants par tables.
Sans un ordre de de distribution de la parole, c'est l'assurance de la cacophonie, style: " C Hanouna".
C'est peut-être pour ça qu'un speed dating comprend seulement deux personnes.

[anapurna]

Bonjour,

Dans votre exemple il y a 45 combinaison possible
Si tu veut retrouver ces combinaison il te suffit de parcourir une
matrice de (n x n) tu trace une diagonale avec les couples identiques
une fois que tu as cette diagonal soit tu prend les éléments au dessus soit au dessous
le résultat et le même. le sens n'ayant que très peux d'importance