Discussion :

[Invité]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

[wiztricks]

Salut,

Je n'arrive pas à vérifier cette double condition dans une seule et unique fonction...

Au pire vous faite une boucle pour vérifier le "dérangement" et une deuxième pour vérifier le "groupe".
Mettre 2 boucles dans une même fonction ne devrait pas poser de problème.
Quand çà marche, vous pourrez essayer de fusionner les 2 boucles en une seule.

- W

[Invité]

Bonjour,

Merci pour votre réponse.
Le problème est comment vérifier le groupe ?
Je m'y suis cassé les dents, mes tentatives ont fait planté littéralement python car la boucle étaient probablement infinie...

[Sve@r]

Bonjour

La fonction Permutation est ainsi définie :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
def permutation(n):
	L=list(range(n))
	rd.shuffle(L)
	return L

La fonction est alors définie comme suit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
def verifDerangement(Perm):
    for i in range(len(Perm)):
        if Perm[i]==i:
            return False
    return True

Hum, cette fonction ne teste en réalité qu'un dérangement sur un tableau ne contenant que des indices ce qui est un peu limité. Elle ne dira jamais si ["a", "b", "c"] est ou n'est pas un dérangement. Ok, admettons que cela suffise...

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...

Ben sais pas, ça me semble pas super compliqué...

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
def verifContrainte(Perm, L):
	if not verifDerangement(Perm): return False
 
	# Ok, Perm convient. Maintenant on va vérifier L...
	... (tout un tas de tests sur L)...
	return True/False   # Selon que L convient ou ne convient pas...

Le problème est comment vérifier le groupe ?
Je m'y suis cassé les dents, mes tentatives ont fait planté littéralement python car la boucle étaient probablement infinie...

Le point de départ est d'arriver à le faire avec un papier et un crayon.

[wiztricks]

Le problème est comment vérifier le groupe ?
Je m'y suis cassé les dents, mes tentatives ont fait planté littéralement python car la boucle étaient probablement infinie...

Vous partez de la proposition "le groupe de celui qui donne départ doit être différent du groupe de celui qui reçoit".

Puis vous essayez de voir à quoi çà peut correspondre avec D = [3, 0, 1, 2] et G = [ 'G1', 'G2', 'G2', 'G3' ] (les prénoms n'ont aucune importance, c'est une juste indirection).

Prenez le premier élément de D, çà traduit 0 donne à 3 (D[0]) et vérifier que G[0] est différent de G[3] et recommencer avec le suivant jusqu'à la fin de la liste ou arrêter dès qu'on à une égalité.

Et cette histoire en français qui dit comment on fait, c'est juste ce qu'on gribouille sur une feuille de papier. Essentiel pour savoir quoi coder car il faut fabriquer le lien entre l'énoncé du problème et sa traduction côté code en structures de données.

- W

[Invité]

Bonjour,

Avec votre aide, voici ce que j'ai pu écrire, j'aimerai avoir votre avis.
Pour moi, cela fonctionne mais il y a peut-être mieux à faire au niveau optimisation, selon vous ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def verifContrainte(Perm,L):
    n = len(L)
    if not verifDerangement(Perm): return False
    ListeMembresC=[]
    for k in range (n):
       ListeMembresC.append((L[k], L[Perm[k]]))
    for matiere1, matiere2 in ListeMembresC:
        if matiere1[1] == matiere2[1]:
            return False
    return True

[wiztricks]

Pour moi, cela fonctionne mais il y a peut-être mieux à faire au niveau optimisation, selon vous ?

optimiser, c'est produire le même résultat avec moins d'instructions, moins de consommation mémoire.

Si vous relisez votre code, une boucle pour construire la liste ListeMembresC, une autre pour tester ses éléments,... pourrait être remplacé par une seule boucle qui teste les éléments (dans laquelle vous pourriez dans un deuxième temps intégrer le test de "derangement").

- W

[Sve@r]

Pour moi, cela fonctionne mais il y a peut-être mieux à faire au niveau optimisation, selon vous ?

Optimiser, ça peut se faire au moment de l'écriture (avec l'habitude on voit ce qui va s'écrire et en même temps comment l'arranger) mais sinon ça se fait après l'écriture. On relit son code et on regarde ce qui se passe. Par exemple

• pourquoi copier len(L) dans "n" alors que "n" n'est utilisé qu'une seule fois
• pourquoi copier len(L) dans "n" si on sort juste après sans avoir utilisé "n"
• pourquoi copier une liste A dans une liste B (sans modification s'entend) et traiter la liste B alors qu'on peut traiter la liste A directement

Optimiser c'est aussi simplement essayer de faciliter la relecture ultérieure ou l'évolution future sans même penser à la vitesse. Par exemple pourquoi copier len(L) dans "n" à 50 lignes de la première utilisation de "n" (ok je dis "50" pour exagérer mais c'est pour illustrer l'idée)

Enfin il y a les optimisations spécifiques à Python et qui viendront avec le temps au fur et à mesure que tes connaissances Python s'étofferont. Par exemple une boucle de ce type

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
dest=[]
for x in iterable:
    if test(x) == resultat: dest.append(travail(x))

Peut s'écrire dest=[travail(x) for x in iterable if test(x) == resultat]. C'est ce qu'on nomme les listes en comprehension (ou en intension, et il n'y a pas d'erreur c'est bien "intension" avec un "s") et ça évite le append() qui est assez lourd.

[Invité]

Merci pour votre précieuse aide et conseil, je retourne continuer la suite, en espérant que ça se passera bien !