Discussion :

[Loceka]

Bonjour bonjour,

J'ai une problématique pour laquelle je pense qu'il existe un algo mais j'ai été incapable de le trouver...

N personnes se rencontrent dans un bar et veulent pouvoir discuter un peu avec tout le monde au cours de la soirée.
Certaines viennent en couple dont le "+1" se fiche de rencontrer tout le monde mais veut rester à côté de sa moitié.
Certaines viennent en couple dont le "+1" veut rencontrer tout le monde mais veut aussi rester à côté de sa moitié.

Etant donné que c'est un bar, on compte qu'une personne peut discuter uniquement avec ses deux voisins directs, son voisin d'en face et les voisins directs du voisin d'en face (donc 5 personnes au max).
Les exceptions étant les bouts de table où, selon la configuration, une personne a soit un voisin d'en face mais pas de voisin direct d'un côté (donc il ne peut parler qu'à 3 personnes), soit pas de voisin d'en face (si elle "préside" ou qu'il y'a un nombre impair de participants) et ne peut donc parler qu'à 2 personnes.

Bon, je doute qu'il existe un algo qui réponde exactement à cette problématique (surtout les couples), mais si vous en connaissez un qui puisse déterminer l'ensemble des placements possibles permettant d'optimiser les déplacements (le moins de déplacements possible), ce serait déjà beaucoup.

Merci d'avance,
Loceka

[Flodelarab]

Bonjour,

que c'est touffu. Il y a un mélange de problèmes bien différents.
Qu'est-ce qui est le plus important ? Que ceux qui veulent voir tout le monde le fasse, ou que les déplacements soient minimum ?

On peut déterminer tous les placements possibles. Surtout si le nombre de convives est petit.

[Loceka]

Merci pour ta réponse !

L'ordre d'importance est

• tout le monde doit se rencontrer
• les couples doivent rester ensemble
• faire le moins de déplacements possibles
• certaines personnes (en couple) n'ont pas besoin de voir tout le monde

Pour info, le nombre de convives serait aux alentour de 20 (un peu moins).