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)

[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

[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 !

[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