Les Trois Tables

Vous préparez une fête et comptez répartir vos 27 invités en 3 tables de 9 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 :

['ALAIN', 'ANNE', 'BERNARD', 'CATHERINE', 'CELINE', 'CHRISTIAN', 'CHRISTOPHE', 'DANIEL', 'DAVID', 'ERIC', 'FRANCOISE', 'FREDERIC', 'JACQUELINE', 'JULIEN', 'LAURENT', 'MARTINE', 'MONIQUE', 'NATHALIE', 'NICOLAS', 'NICOLE', 'PHILIPPE', '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 liste, et les listes entre elles), et il peut y avoir plusieures répartitions différentes qui satisfont toutes les contraintes données.

Ce problème est tiré de c0d1ng UP 2014

Type de retour

Une séquence contenant trois séquences de prénoms

Entrée du problème

[('DAVID', 'ALAIN'), ('NICOLAS', 'ALAIN'), ('ALAIN', 'SOPHIE'), ('DAVID', 'BERNARD'), ('ERIC', 'BERNARD'), ('BERNARD', 'SOPHIE'), ('BERNARD', 'STEPHANE'), ('CATHERINE', 'CHRISTOPHE'), ('CELINE', 'CHRISTOPHE'), ('CHRISTOPHE', 'DANIEL'), ('NICOLAS', 'CHRISTOPHE'), ('PHILIPPE', 'CHRISTOPHE'), ('CHRISTOPHE', 'VALERIE'), ('CHRISTOPHE', 'VERONIQUE'), ('DANIEL', 'CELINE'), ('DANIEL', 'CHRISTIAN'), ('ERIC', 'DANIEL'), ('DANIEL', 'SOPHIE'), ('ANNE', 'FRANCOISE'), ('FRANCOISE', 'DAVID'), ('FRANCOISE', 'ERIC'), ('JULIEN', 'FRANCOISE'), ('FRANCOISE', 'STEPHANIE'), ('VALERIE', 'FRANCOISE'), ('ANNE', 'FREDERIC'), ('FREDERIC', 'PHILIPPE'), ('SOPHIE', 'FREDERIC'), ('FREDERIC', 'STEPHANE'), ('FREDERIC', 'VALERIE'), ('JACQUELINE', 'ANNE'), ('ERIC', 'JACQUELINE'), ('JACQUELINE', 'STEPHANIE'), ('SOPHIE', 'JULIEN'), ('STEPHANIE', 'JULIEN'), ('CELINE', 'LAURENT'), ('CHRISTIAN', 'LAURENT'), ('SOPHIE', 'LAURENT'), ('CATHERINE', 'MARTINE'), ('MARTINE', 'CHRISTIAN'), ('DAVID', 'MARTINE'), ('ERIC', 'MARTINE'), ('MARTINE', 'SOPHIE'), ('MONIQUE', 'ANNE'), ('BERNARD', 'MONIQUE'), ('MONIQUE', 'DANIEL'), ('MONIQUE', 'DAVID'), ('MONIQUE', 'JULIEN'), ('PHILIPPE', 'MONIQUE'), ('MONIQUE', 'STEPHANE'), ('VALERIE', 'MONIQUE'), ('VERONIQUE', 'MONIQUE'), ('NATHALIE', 'CATHERINE'), ('DAVID', 'NATHALIE'), ('NATHALIE', 'LAURENT'), ('BERNARD', 'NICOLE'), ('NICOLE', 'DAVID'), ('NICOLE', 'LAURENT'), ('NICOLE', 'PHILIPPE'), ('NICOLE', 'STEPHANE'), ('NICOLE', 'VALERIE'), ('PHILIPPE', 'CELINE'), ('PHILIPPE', 'DAVID'), ('NICOLAS', 'PHILIPPE'), ('SOPHIE', 'PHILIPPE'), ('STEPHANE', 'PHILIPPE'), ('ANNE', 'SYLVIE'), ('BERNARD', 'SYLVIE'), ('SYLVIE', 'CATHERINE'), ('SYLVIE', 'CELINE'), ('DAVID', 'SYLVIE'), ('LAURENT', 'SYLVIE'), ('SYLVIE', 'MARTINE'), ('SYLVIE', 'PHILIPPE'), ('SYLVIE', 'SOPHIE'), ('SYLVIE', 'VERONIQUE'), ('VALERIE', 'CATHERINE'), ('STEPHANE', 'VALERIE'), ('STEPHANIE', 'VALERIE'), ('VERONIQUE', 'CELINE'), ('ERIC', 'VERONIQUE'), ('SOPHIE', 'VERONIQUE')]

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup14 combinatoire algo