Les Trois Tables

Ce défi est tiré de c0d1ngUP 2014

Vous préparez une fête et comptez répartir vos 30 invités en 3 tables de 10 personnes.

Vos invités sont toutefois difficiles et ne s'entendent pas tous très bien. Pour éviter les coups d'éclat, vous disposez d'une liste de couples de personnes qui ne peuvent en aucun cas être placés à la même table.

Voici déjà la liste de tous les convives : 

['ANNE', 'BERNARD', 'CELINE', 'CHRISTINE', 'CHRISTOPHE', 'DANIEL', 'ERIC', 'FREDERIC', 'JEANNE', 'JULIEN', 'LAURENT', 'MARIE', 'MARTINE', 'MICHEL', 'MONIQUE', 'NATHALIE', 'NICOLAS', 'NICOLE', 'PASCAL', 'PATRICK', 'PHILIPPE', 'PIERRE', 'SANDRINE', 'SEBASTIEN', 'SOPHIE', 'STEPHANE', 'STEPHANIE', 'SYLVIE', 'VALERIE', 'VERONIQUE']

L'entrée du problème est la liste des couples de personnes qui ne peuvent être placés à la même table. Vous devez fournir comme réponse au problème une séquence de 3 séquences de prénoms indiquant une répartition par table qui satisfait toutes les contraintes.

Voici un exemple, avec seulement 9 personnes (donc 3 par tables) :

  • liste des noms ['ALBERT', 'JEAN', 'MICHEL','MARIUS','STEPHANIE','NICOLE', 'LAURENT','STEPHANE','JEANNE']
  • la liste des couples incompatibles : [('ALBERT','JEAN'),('ALBERT','NICOLE'),('STEPHANE','MICHEL'),('NICOLE','STEPHANIE'), ('STEPHANIE','ALBERT'),('STEPHANIE','JEANNE')]

Avec ces entrées, un placement correct est :

  • Table 1 : ALBERT, LAURENT, JEANNE
  • Table 2 : JEAN, STEPHANIE, MICHEL
  • Table 3 : MARIUS, NICOLE, STEPHANE

Pour cet exemple, une réponse valide serait donc : 

('ALBERT', 'LAURENT', 'JEANNE'), ('JEAN', 'STEPHANIE', 'MICHEL'), ('MARIUS', 'NICOLE', 'STEPHANE')
Naturellement, il y a plusieurs façons de coder la même répartition par table (on peut intervertir les noms dans une séquence, et les séquences entre elles), et il peut y avoir plusieurs répartitions différentes qui satisfont toutes les contraintes données.

Type de retour
Une séquence contenant trois séquences de prénoms
Entrées du problème

[('ANNE', 'PHILIPPE'), ('VALERIE', 'ANNE'), ('ANNE', 'VERONIQUE'), ('MARTINE', 'BERNARD'), ('SANDRINE', 'CELINE'), ('SEBASTIEN', 'CELINE'), ('VALERIE', 'CELINE'), ('CHRISTINE', 'DANIEL'), ('CHRISTINE', 'JULIEN'), ('LAURENT', 'CHRISTINE'), ('MICHEL', 'CHRISTINE'), ('CHRISTINE', 'NATHALIE'), ('CHRISTINE', 'SEBASTIEN'), ('STEPHANE', 'CHRISTINE'), ('CHRISTINE', 'SYLVIE'), ('CELINE', 'CHRISTOPHE'), ('DANIEL', 'CHRISTOPHE'), ('NICOLE', 'CHRISTOPHE'), ('PHILIPPE', 'CHRISTOPHE'), ('SEBASTIEN', 'CHRISTOPHE'), ('CHRISTOPHE', 'STEPHANE'), ('CHRISTOPHE', 'SYLVIE'), ('VALERIE', 'CHRISTOPHE'), ('ERIC', 'LAURENT'), ('ERIC', 'MARTINE'), ('ERIC', 'PHILIPPE'), ('ERIC', 'VALERIE'), ('ERIC', 'VERONIQUE'), ('ANNE', 'FREDERIC'), ('FREDERIC', 'BERNARD'), ('CELINE', 'FREDERIC'), ('FREDERIC', 'JULIEN'), ('FREDERIC', 'LAURENT'), ('FREDERIC', 'SANDRINE'), ('STEPHANE', 'FREDERIC'), ('BERNARD', 'JEANNE'), ('JEANNE', 'DANIEL'), ('JULIEN', 'JEANNE'), ('LAURENT', 'JEANNE'), ('JEANNE', 'MONIQUE'), ('JEANNE', 'SANDRINE'), ('JEANNE', 'SEBASTIEN'), ('JULIEN', 'MARTINE'), ('NATHALIE', 'JULIEN'), ('CELINE', 'MARIE'), ('ERIC', 'MARIE'), ('MARIE', 'JULIEN'), ('MARIE', 'MONIQUE'), ('NATHALIE', 'MARIE'), ('SEBASTIEN', 'MARIE'), ('MARIE', 'STEPHANE'), ('SYLVIE', 'MARIE'), ('DANIEL', 'MICHEL'), ('MICHEL', 'PHILIPPE'), ('SANDRINE', 'MICHEL'), ('VALERIE', 'MICHEL'), ('VERONIQUE', 'MICHEL'), ('PHILIPPE', 'NICOLAS'), ('NICOLAS', 'SEBASTIEN'), ('NICOLAS', 'VALERIE'), ('NICOLE', 'DANIEL'), ('NICOLE', 'LAURENT'), ('MONIQUE', 'NICOLE'), ('NICOLE', 'NATHALIE'), ('PHILIPPE', 'NICOLE'), ('SANDRINE', 'NICOLE'), ('NICOLE', 'SEBASTIEN'), ('NICOLE', 'VALERIE'), ('PASCAL', 'DANIEL'), ('PASCAL', 'JULIEN'), ('PASCAL', 'MICHEL'), ('PASCAL', 'NATHALIE'), ('PASCAL', 'SANDRINE'), ('PASCAL', 'SEBASTIEN'), ('SYLVIE', 'PASCAL'), ('PATRICK', 'ANNE'), ('PATRICK', 'CELINE'), ('PATRICK', 'JULIEN'), ('MARTINE', 'PATRICK'), ('PATRICK', 'NICOLAS'), ('NICOLE', 'PATRICK'), ('SEBASTIEN', 'PATRICK'), ('PATRICK', 'STEPHANE'), ('PIERRE', 'CELINE'), ('PIERRE', 'DANIEL'), ('PIERRE', 'LAURENT'), ('PIERRE', 'MONIQUE'), ('PIERRE', 'NATHALIE'), ('SYLVIE', 'PIERRE'), ('VALERIE', 'PIERRE'), ('SOPHIE', 'DANIEL'), ('MARTINE', 'SOPHIE'), ('SOPHIE', 'SEBASTIEN'), ('SOPHIE', 'STEPHANE'), ('SANDRINE', 'STEPHANE'), ('STEPHANIE', 'BERNARD'), ('STEPHANIE', 'LAURENT'), ('MARTINE', 'SYLVIE'), ('SEBASTIEN', 'SYLVIE'), ('SYLVIE', 'VALERIE')]

Vous devez être connecté.e pour proposer une réponse au défi
Vous devez être connecté.e pour accéder aux forums.
cup14 combinatoire algo