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