Débutant - utilisation des permutations avec des contraintes
Bonjour,
Je suis nouveau sur le forum et je me permets de vous solliciter car depuis 2 jours et plusieurs heures de recherche je reste bloqué sur une question d'un travail que je dois faire pour m'entraîner au langage Python.
Je dois répondre à un problème qui commence... par une liste que voici :
Code:
1
2
3
| Membres = [('Tessa','G1'),('Evan','G2'),('Tom','G3'),
('Mia','G3'),('Claire','G3'),('Billie','G4'),('Adrian','G2'),('Maddie','G1'),
('Lewis','G1'),('Tony','G2'),('Joyce','G1'),('Julian','G5'),('Joshua','G2')('Warren','G3')] |
Cette liste représente une liste de résidents et à côté, des groupes. Ces groupes ont été tiré au sort à la main.
Le but est de créer à la fin des couples de deux individus qui vont s'offrir un cadeau pour Noël.
A partir de cette liste, je dois écrire une fonction verifContrainte(Perm,L) qui prend en compte deux paramètres :
- Perm : qui est une fonction qui construit au hasard une permutation des entiers de 0 à n-1 et la retourne.
- L : la liste Members sous forme ('Prénom d'un résident','Groupe d'appartenance')
La fonction Permutation est ainsi définie :
Code:
1
2
3
4
5
6
7
8
9
10
11
| def permutation(n):
L=[]
Perm=[]
j=0
for i in range(n):
L.append(i)
for k in range(n):
alea = rd.randint(0,len(L)-1)
j=L.pop(alea)
Perm.append(j)
return Perm |
Précédemment pour les besoins de l'exercice, j'ai écris une fonction verifDerangement(Perm) qui ne prenait en argument qu'une permutation en argument. Le dérangement est une permutation pour laquelle aucun de ses éléments n'est à sa place d'origine. Par exemple, parmi les 6 permutations des entiers de 0 a 2, il existe deux dérangements : ce sont [1,2,0] et [2,0,1].
L'intérêt du dérangement est donc de changer l'ordre de la liste de manière à ce que chaque résident offre son cadeau à un autre résident et non pas à lui-même. La fonction est alors définie comme suit :
Code:
1
2
3
4
5
6
|
def verifDerangement(Perm):
for i in range(len(Perm)):
if Perm[i]==i:
return False
return True |
Là, je dois créer une nouvelle fonction verifContrainte(Perm,L) qui doit aussi prendre une liste L de couples (résident, groupe), la fonction doit juger si la permutation en entrée vérifie deux critères :
- si c'est bien un dérangement (pour que le résident ne donne pas son cadeau à lui-même) ce qui est le cas lorsque Perm[k] vaut k pour un certain cas
- si aucun résident n'offre de cadeau à un résident de son propre groupe
Cette fonction doit renvoyer True si Perm vérifie les contraintes de groupe False sinon.
Par exemple,
Code:
1
2
3
4
5
6
|
>>>> verifContrainte([2, 3, 0, 1],[('Tessa','G1'),('Evan','G2'),('Tony','G2'),('Warren','G3')])
True
>>>> verifContrainte([3, 0, 1, 2],[('Tessa','G1'),('Evan','G2'),('Tony','G2'),('Warren','G3')])
False |
Le dernier retourne False car Tony (du groupe 2) offre son cadeau à Evan (du groupe 2 également).
Jusqu'à alors, je m'inspirais de verifDerangement mais je n'arrive pas à obtenir le résultat escompté... Je n'arrive pas à vérifier cette double condition dans une seule et unique fonction...
Peut-être avez vous une piste...
