- J'ai une liste L1 constituée d'un nombre connu d'élements
- J'ai une liste L2 de même longueur que L1 ( longueur n )
Je dois écrire une fonction python qui renvoie le nombre d'élements communs des deux listes ayant des indices différents. Cette fonction ne doit pas prendre ne compte les éléments communs si ils sont à la même position.
J'ai écris ceci :
def communs(L1,L2):
r=0
i=0
for j in range(n):
for i in range(n):
if ( L2[j]==L1[i] and i!= j ):
r+=1
return r
Mais j'ai un problème quand L1 possède des doublons :par exemple pour L1=[1,1] et L2=[0,1], ma fonction renvoie 1 au lieu de 0...
Est-ce que quelqu'un a une solution à ce problème ? Merci d'avance !
Tu dois aussi gérer le cas où tu as plusieurs versions d'une valeur:
lst1 = [1, 1, 1, 1, 1, 1, 2]
lst2 = [0, 0, 0, 0, 0, 0, 1]
#commun(lst1, lst2) # -> 6 (alors que la bonne réponse est 1)
Sinon tu itères sur n (lignes 4 et 5) alors que celle-ci n'a pas été définie, et l'initialisation de i (ligne 3) est inutile.
PS: Utilise le bouton </> pour insérer du code sur le forum
EDIT: Cet exercice n'est pas si simple que ça en fait. Pour ma part, j'ai réussi à trouver une solution assez simple en remplaçant les valeurs déjà inspectées par None (en supposant que None n'est pas un élément possible des séquences). Sans ça, je trouve que c'est un exo assez chaud pour un débutant
Ah merci,je n'avais pas pris en compte ce problème.. Désolé je suis nouveau sur ce forum, je cherchais justement comment faire du code plus proprement pour mes messages..
n est une variable fixé dans l'exercice ( en dehors de ma fonction ). Ah oui, cette initialisation ne sert à rien en effet merci !
[EDIT] :
En réalité la finalité de cet exercice est de créer le jeu Mastermind, les valeurs de la liste représentent des couleurs, donc None ne peut pas en faire partie.. Je suis également bloqué sur une autre mais elle nécessite que celle-ci fonctionne, je fais donc étape par étape
L'idée serait donc d'inspecter l'élément et après de le remplacer par None, ce qui l'empêcherait d'être à nouveau compté ? ?
- Edité par Pythonislife 27 octobre 2016 à 13:01:41
J'ai voulu tester, je suis tombé face au même problème qu'@Olygrim; mais je l'ai pas résolu de la même manière:
je commence avec un set vide (je l'ai appelé visited par manque de gout)
on parcourt l1: si un element de l1 est dans l2 ET qu'il n'est pas dans visited, alors le compteur augmente et on ajoute cet element dans visited.. (PS: je fais exprès de ne pas balancer le code histoire que le PO s'amuse)
Ca permet d'être aussi fonctionnel que la méthode d'@Olygrim, mais en moins dégueu qu'avec des None à tout va
Elle a l'air de marcher pas trop mal..
EDIT: je suis entrain de penser @Olygrim, ta méthode, tu modifies la liste que tu es entrain de parcourir du coup? Oo'
- Edité par WexyR 27 octobre 2016 à 13:22:50
Si je suis tête en l'air, c'est par habitude de viser le sommet
lst1 = [1, 1, 1, 1, 1, 1, 2]
lst2 = [0, 0, 0, 0, 0, 0, 1]
#commun(lst1, lst2) # -> 6 (alors que la bonne réponse est 1)
je croyais qu'on devait pas prendre en compte si y'en avait plusieurs occurences du même élément dans l1 du coup la mienne renvoit 1
Olygrim a écrit:
WexyR a écrit:
mais en moins dégueu qu'avec des None à tout va
Oh le méchant
On va pas se mentir, c'est moche x)
Bon alors je modifie et je reviens dans 10 min
EDIT: bon c'est long à expliquer alors je post le code (vous vous en plaindrez à ma flemmardise)
def commun(l1, l2):
visited = set()
c = 0
for elt1 in l1:
for index, elt2 in enumerate(l2):
if elt1 == elt2 and index not in visited:
c += 1
visited.add(index)
break
return c
pour faire court mon set ne contient non plus les elements à eviter mais l'index des element à éviter.
étant donné que faire un in revient à parcourir toute la liste l2, je préfère le faire moi-même, comme ca je récupère l'index.
Je pense pas perdre trop de temps ni de mémoire en faisant ça, vous en pensez quoi?
- Edité par WexyR 27 octobre 2016 à 14:00:15
Si je suis tête en l'air, c'est par habitude de viser le sommet
En fait je pense que ma solution n'est pas bonne également si on se place dans le contexte d'un mastermind (qui est au final l'objectif de la fonction). Avec les deux listes précédentes, la fonction devrait renvoyer 0.
EDIT: Normalement j'ai réussi à corriger ma fonction (en gardant toujours cette fantastique solution avec les None)
def common_items(seq1, seq2):
common = 0
seq2 = list(seq2)
for index1, item1 in enumerate(seq1):
for index2, item2 in enumerate(seq2):
if item1 == item2:
if item1 == seq2[index1]:
break
elif seq1[index2] != item2:
common += 1
seq2[index2] = None
break
return common
PS: Ah bah si en fait je fais une copie (ligne 3). J'avais zappé ce détail
les éléments reliés par un trait on bien la même valeur et un indice différents. Du coup ça a du mal à marcher.. je vois pas trop comment contourner le problème sans faire un truc du même genre que toi @Olygrim x)
je vais continuer de réfléchir mais bon..
Je me demandais, en passant par la fonction count, on a pas possibilité de faire un truc bien?
Si je suis tête en l'air, c'est par habitude de viser le sommet
Il faut que je développe mes compétences algorithmiques (je suis pas super fort là-dessus). C'est pour ça que j'essaie de réfléchir à des algorithmes naïfs mais efficace
Mais j'avoue que je n'ai pas eu de *flash* me permettant d'utiliser l'un ou l'autre de ces modules
Ton code ne renvoie pas toujours le bon résultat. Par exemple pour les deux listes suivantes:
lst1 = [3, 2, 0, 1, 1]
lst2 = [1, 1, 3, 2, 1]
Il y a 3 valeurs mal placées (le 3, le 2 et le 1) mais ton code renvoie 2. Par contre je ne pourrais absolument pas te dire pourquoi car j'ai pas compris grand chose à ton code
Une tentative... j'ai regardé les règles du master mind
def necommuns(liste_a,liste_b):
assert len(liste_a) == len(liste_b)
# On enlève les éléments identiques qui sont à la même position
# On doit faire cette détection de toute façon pour savoir
# si le joueur a proposé les bonnes couleurs dans sa ligne
# de mastermind, donc autant faire d'une pierre deux coups...
A = []
B = []
for n in xrange(len(liste_a)):
if liste_a[n] == liste_b[n]:
print "position %d est bonne" % n
else:
A.append(liste_a[n])
B.append(liste_b[n])
print "reste:", A,B
# on cherche les éléments communs
# Note pour le mastermind:
# si la combinaison gagnante est 1122 et on propose 2211
# alors on a 4 éléments corrects mais pas au bon endroit,
# on doit donc renvoyer 4
# MAIS si la combi on propose 1112, alors le 2 est bon,
# les deux premiers 1 sont bons, et le 3ème 1
# ne compte pas, on renvoie donc 0!
compte = 0
for a in A:
if a in B:
B.remove(a)
compte += 1
return compte
a = [1,2,3,1,1,3]
b = [1,3,2,2,1,3]
print ">",necommuns(a,b)
a = [1,1,2,2]
b = [2,2,1,1]
print ">",necommuns(a,b)
a = [1,1,2,2]
b = [1,1,1,2]
print ">",necommuns(a,b)
Ton code ne renvoie pas toujours le bon résultat. Par exemple pour les deux listes suivantes:
lst1 = [3, 2, 0, 1, 1]
lst2 = [1, 1, 3, 2, 1]
Il y a 3 valeurs mal placées (le 3, le 2 et le 1) mais ton code renvoie 2. Par contre je ne pourrais absolument pas te dire pourquoi car j'ai pas compris grand chose à ton code
c'est pas ce qui est demandé ? ... arf, j'avais pas compris l'énoncé.
Edit:
donc ici on parle de MasterMind ... ça tombe bien j'en avais codé un : ici
et la fonction qui nous intéresse:
def submit(mastermind,value):
try:
a,b = zip(*[(a,b) for a,b in zip(mastermind,value) if a!=b])
a = list(a)
except: return 4,0
for i in b:
try: a.remove(i)
except: continue
return 4-len(b),len(b)-len(a) # retourne bien placés, mal placés
Ok, la logique est la même que pour la fonction de Casque Noir:
Récupérer les éléments qui ne sont pas identiques dans deux listes séparées.
Itérer sur l'une et supprimer dans l'autre si l'élément est présent.
J'aime beaucoup
Voici ma version copitée de celle de Casque Noir :
def items_common(seq1, seq2):
assert len(seq1) == len(seq2)
items_seq1, items_seq2 = [], []
for item1, item2 in zip(seq1, seq2):
if item1 != item2:
items_seq1.append(item1), items_seq2.append(item2)
compte = 0
for item1 in items_seq1:
if item1 in items_seq2:
items_seq2.remove(item1)
compte += 1
return compte
variante de algo classique de fusion/union/intersection de listes ordonnées
Un truc comme ça
def communs(liste1, liste2):
l1 = liste1[:] # copies
l2 = liste2[:]
l1.sort()
l2.sort()
i = 0
j = 0
nb = 0
while (i < len(l1) and j < len(l2)):
if l1[i] < l2[j] :
i += 1
elif l1[i] > l2[j] :
j += 1
else:
nb += 1
i += 1
j += 1
return nb
Ca compte ceux qui sont à la même place, mais c'est facile de les soustraire ensuite (d'autant que si c'est le mastermind, on a besoin de les compter de toutes facons)
PS : sur des listes de grande taille, ça doit être optimal ( N log N dû au tri), mais bon, sur un master mind avec des listes de longueur 4, la methode triviale de comparaison 2 à 2, ça fait jamais que 16 comparaisons.
- Edité par michelbillaud 28 octobre 2016 à 11:33:49
La difficulté c'est justement de faire un code qui ne prend pas en compte les éléments à la même place. Sinon si c'est juste un décompte, il suffit d'écrire:
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.