Discussion :

[Isabella83]

Bonjour!!!
J'ai une liste de ce type a trier :

Liste = [("A",4),("B",3),("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]

Cette liste represente, par exemple, le nombre d'occurence de chaque lettre dans un texte : si l'utilisateur tape occurence(texte,k) : la fonction retourne les K lettres les plus abondantes dans le texte, donc dans ma liste qui compte le nombre d'occurence de chaque lettre ( j'ai deja ecrit un fonction qui fait ca et qui en plus les trie par ordre croissant).

donc, j'ai ecrit cette fonction :



Code :

occurence(texte,k):
ListeTriee=[]
ListeRetour=[]
Liste= [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
print Liste
for i in range(len(Liste)):
while i<range(len(Liste)):
if Liste[i][1] != Liste[i+1][1] and j<k :
ListeRetour.append(Liste[i+1])
j=j+1
elif Liste[i][1] == Liste[i+1][1]:
ListeRetour.append(Liste[i+1][1])
return ListeRetour
En fait, je voulais un resultat sous forme de liste, qui renvoi les k lettres les plus abondante, et que si plusieurs lettres ont la meme occurence, elles doivent etre inserée dans la liste jusqu'a ce que on est les K lettre les plus abondantes :

Par exemple, ici, si l'utilisateur tape
occurence('texte',3), on doit avoir [ "A","B","J"]

Ma fonction ne marche pas ... Quelqu'un aurait il la gentillesse de m'aider ?
Merci.

[tyrtamos]

Bonjour,

On n'a pas besoin de trier pour extraire les lettres dont l'occurrence est supérieure ou égale à une valeur donnée n. Mais, bien sûr, dans ce cas, la liste résultat respecte l'ordre de la liste initiale:

Code :

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

1
2
3
4
5
6
 
Liste = [("A",4),("B",0),("C",2),("D",1),("E",2),("F",3),("G",1),("H",5),("D",1)]
 
n = 3
print [lettre for lettre, nombre in Liste if nombre>=n]
['A', 'F', 'H']

On peut même fabriquer une fonction qui fait ça:

Code :

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

1
2
3
4
5
 
freqlettre = lambda n, Liste: [lettre for lettre, nombre in Liste if nombre>=n]
 
print freqlettre(n, Liste)
['A', 'F', 'H']

Mais si tu veux trier, voilà comment faire: il faut créer une fonction de comparaison et utiliser la méthode sort() de Python. Ici, on trie dans l'ordre décroissant du nombre d'occurrences:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
def compfreq(elem1,elem2):
    if elem1[1]<elem2[1]:
        return -1
    if elem1[1]>elem2[1]:
        return 1
    return 0
 
Liste.sort(compfreq, reverse=True)
 
print Liste
[('H', 5), ('A', 4), ('F', 3), ('C', 2), ('E', 2), ('D', 1), ('G', 1), ('D', 1), ('B', 0)]

[et utilise les tag de code: python sans indentation est incompréhensible]

Tyrtamos

[Isabella83]

J'ai du mal m'exprimer, en fait dans votre exemple , n correspond " au nombre de fois où elles apparaissent" et moi ce que je veux c'est que n corresponde aux "n lettres les plus abondantes"

[Isabella83]

C'est pour cela que j'ai cree une fonction qui me les met dans l'ordre en fonction de leur nombre d'occurence ...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def occurence(texte,k):
ListeTriee=[]
ListeRetour=[]
Liste= [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
print Liste
for i in range(len(Liste)):
 while i<range(len(Liste)):
  if Liste[i][1] != Liste[i+1][1] and j<k :
   ListeRetour.append(Liste[i+1])
   j=j+1
 elif Liste[i][1] == Liste[i+1][1]:
  ListeRetour.append(Liste[i+1][1])
 return ListeRetour

[eyquem]

Bonjour !!! Bienvenue



Dans ton code le compteur est manifestement j, mais il n’est pas initialisé.



Les deux lignes suivantes, bien qu’un peu différentes, sont redondantes:

for i in range(len(Liste)):
while i<range(len(Liste)):

Il faut choisir: soit on boucle avec while, soit avec for.




Si i parcourt range(len(Liste)) , il y aura un problème pour i==len(Liste)-1 , repérant le dernier élément, car alors i+1 vaudra len(Liste) c’est à dire erreur “index out of range“ pour Liste[i+1]

D’où nécessité de boucle for i in range(len(Liste)-1) et faire un test supplémentaire après sortie de la boucle.





Mais il y a un autre problème dans ton code: tu ne fais append() que sur un élément en i+1 , donc, comme i commence à 0, tu enregistres à partir de l’élément 1: le premier élément est oublié.


Il faut donc en fait revoir ton algorithme de façon un peu notable.

Au lieu de faire un test par rapport à l’élément suivant il faut comparer l’élément d’index i envisagé avec ce qui le PRÉCÈDE.


Le code suivant , avec cette correction mais dans l’esprit du tien, marche.
Mais je posterai plus tard un code amélioré sur certains points.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Liste= [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
print Liste
 
ListeRetour=[]
j = 0
k = 3
frequ_prec = 0
for i in range(len(Liste)):
    if Liste[i][1] != frequ_prec:
        if j<k :
            ListeRetour.append(Liste[i][0])
            j=j+1
        else:
            break
    else:
        ListeRetour.append(Liste[i][0])
print ListeRetour

[Isabella83]

Merci beaucoup d'avoir regardé !
Votre programme fonctionne pour k=3, mais si on met k=4, il nous sort seulement "C", alors qu'il devrait y avoir egalement "D", "E", "F", qui ont la meme occurence que "C", et c'est justement cela mon problème et la raison de mon post ...

[eyquem]

Parce que je suis un gros bêta trop pressé.

Tu devrais pouvoir trouver l’erreur toute seule en 1 mn d'examen

[Isabella83]

C'est si evident que ca ? Ca fait deux jours que je cherche, j'ai essayé de transformé en dico , mais ca n'a rien donné ...

[eyquem]

il ne faut pas croire que les étoilés ne font jamais d’erreur. J’ai oublié une instruction dans MON code , ce n’est pas le tien qui est en cause

[Isabella83]

L'erreur est humaine
l'instruction "oubliée" et que si frequ_prec = Liste[i][1] alors on ajoute ListeRetour.append(Liste[i][0]) et on n'increment pas j ???

[eyquem]

Ah ben non ! , on n’incrémente surtout pas j quand on traite une lettre dont la fréquence est la même que celle de la lettre précédente

Sinon, si on incrémente j dans tous les cas, il sert à quoi le j ?

Par contre, pourquoi ai-je donc introduit freq_prec avec une valeur fixée à 0 ??.....





Pas mal l’idée du dico, c’est ce qu’il faut faire en fait, oui, ce sera mieux.

Tu as des difficultés à constituer ton dico ? Qu’y a-t-il en amont de Liste ? Le texte ou une structure de données intermédiaires ? Comment construis tu ta Liste ?

[Isabella83]

En fait, j'ai pri la liste avec l'occurence des lettre pour imager mon problème ....
A la base, j'ai un dictionnaire du type

{ "A":4, "B":3 } etc ...

Mais je l'ai transformé en liste, afin de pouvoir le trier, de la facon dont je vous l'ai montré en haut ...

Et donc, je pense que desormais vous avez compri mon problème ...

Et le dico que je voulais creer etait du coup de la forme

{3:"A",2:"C","D" } etc
Mais on ne peut pas mettre de type str dans un append ... donc, j'etais bloquée

[eyquem]

Oui, oui, bien compris. On va optimiser un peu tout ça.



D’abord pour ne pas faire trainer les choses en longueur:

freq_prec est introduite dans le code pour permettre de comparer une fréquence à la position i à la fréquence à la position i-1.

Au départ, freq_prec est initialisée à 0 car le premier élément de la liste aura certainement une fréquence différente de 0.

Mais pour le deuxième, il faudrait comparer sa fréquence à cette fréquence du premier élément. Or on compare à freq_prec qui est restée à 0....

Conclusion: quand Liste[i][1]!=freq_prec il faut quefreq_prec prenne cette valeur de Liste[i][1]



la suite dans un instant

[Isabella83]

Non, je n'ai aucune ocurence egale a 0 de toute facon !
J'ai essayé de modifié mon programme mais ca ne me sort pas les autres occurences !
Vous pensez qu"on peut realiser ce que je veux faire avec un liste, ou plutot avec un dico?

[eyquem]

Quand on ajoute l’une après l’autre des lettres dans ListeRetour, la longueur de ListeRetour augmente de 1 à chaque fois, mais cette longueur n’est pas représentative du nombre de fréquences différentes associées à ces lettres ajoutées.

On est alors obligé de créer un compteur j qui s’incrémente non plus à chaque ajout de lettre, mais à chaque fois qu’une lettre avec une fréquence différente est ajoutée. Il faut pour cela un test, auquel on est obligé de consacrer des lignes.

len(ListeRetour) mesure la longueur de ListeRetour
et j compte le nombre de fréquences différentes

Ce qui serait bien, c’est de disposer , non pas d’un compteur des fréquences différentes, mais d’un conteneur des fréquences différentes.

La longueur de ce conteneur donnerait directement le nombre de fréquences différentes déjà vues dans l’extraction de Liste vers ListeRetour.



Un tel conteneur existe: un ensemble

Quand on ajoute un élément à un ensemble dans lequel il se trouve déjà, cela ne change rien au contenu de l’ensemble. Tous les éléments d’un ensemble sont différents deux à deux, c’est le propre de la structure de donnée “ensemble“ en Python



D’où le code:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
Liste= [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",0)]
print Liste
 
ListeRetour=[]
s = set([])
k = 4
for i in range(len(Liste)):
    s.add(Liste[i][1])
    if len(s)==k+1:
        break
    ListeRetour.append(Liste[i][0])
 
print ListeRetour

Et en tenant compte de la facilité à itérer dans une liste sans passer par un index qu’offre Python:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
Liste= [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",0)]
print Liste
 
ListeRetour=[]
s = set([])
k = 4
for u in Liste:
    s.add(u[1])
    if len(s)==k+1:
        break
    ListeRetour.append(u[0])
 
print ListeRetour

Une petit dépaquetage de données, et hop:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
Liste= [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",0)]
print Liste
 
ListeRetour=[]
s = set([])
k = 4
for lettre,frequ in Liste:
    s.add(frequ)
    if len(s)==k+1:
        break
    ListeRetour.append(lettre)
 
print ListeRetour

[Isabella83]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
Liste= [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",0)]
print Liste
 
ListeRetour=[]
s = set([])
k = 4
for lettre,frequ in Liste:
    s.add(frequ)
    if len(s)==k+1:
        break
    ListeRetour.append(lettre)
 
print ListeRetour

Je n'ai pas bien compri l'interet de s.add(frequ)??
C'est pour que si deux freq sont les meme, du coup, len(s) ne change pas, et de ce fait on continue d'ajouter la lettre correspondante a notre ListeRetour ?

En tout cas, merci beaucoup d'avoir pri le temps de trouver une solution a mon probleme, c'est vraiment très gentil

[eyquem]

Pour ce qui est de la correction du code déficient à cause de freq_prec non modifiée, et puisqu’apparemment tu ne vois pas ce qu’il faut faire:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Liste= [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
print Liste
 
ListeRetour=[]
j = 0
k = 3
frequ_prec = 0
for i in range(len(Liste)):
    if Liste[i][1] != frequ_prec:
        if j<k :
            frequ_prec = Liste[i][1]
            ListeRetour.append(Liste[i][0])
            j=j+1
        else:
            break
    else:
        ListeRetour.append(Liste[i][0])
print ListeRetour

En utilisant le dépaquetage de données (unpacking),

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Liste= [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
print Liste
 
ListeRetour=[]
j = 0
k = 3
frequ_prec = 0
for lettre,frequ in Liste:
    if frequ != frequ_prec:
        if j<k :
            frequ_prec = frequ
            ListeRetour.append(lettre)
            j=j+1
        else:
            break
    else:
        ListeRetour.append(lettre)
print ListeRetour

Note qu’on peut réorganiser le code: avant de regarder si la fréquence et la fréquence précédente sont identiques on regarde si j<k ou non, c’est à dire s’il faut continuer ou s’arrêter.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Liste= [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
print Liste
 
ListeRetour=[]
j = 0
k = 3
frequ_prec = 0
for lettre,frequ in Liste:
    if j<k:
        if frequ != frequ_prec:
            frequ_prec = frequ
            j=j+1
        ListeRetour.append(lettre)
    else:
        break
print ListeRetour

Mais personnellement je préfère une solution avec set.

[wiztricks]

J'écrirai plutôt cela ainsi

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
def occurence(texte,k):
    strip_count = lambda li: [ c[0] for c in li ]
    if k >= len (texte): 
        return strip_count(texte)
    r = texte[:k]          # les k premiers
    last = r[-1:][0]       # l'occurence du dernier
 
    for e in texte[k:]:    # si l'occurrence du suivant est...
        if e[1] != last[1]: # differente, on sort
            break
        r.append(e)        # egale, on garde
    return strip_count(r)
 
 
 
Liste=  [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
print occurence(Liste, 4)

-W
Note: Suppose la liste rangée par occurences décroissante.

[Isabella83]

D'accord !!!
Merci beaucoup

[eyquem]

@ Isabella83

C'est pour que si deux freq sont les meme, du coup, len(s) ne change pas, etc

Je dirais plutôt:
C’est pour que si la fréquence examinée est déjà présente dans l’ensemble s, len(s) ne change pas,etc
Mais oui, c’est ça.


Ça consiste à reporter sur l’ensemble s la tâche de vérifier si on est arrivé à un élément de fréquence différente.

Comme ce test à l’entrée dans l’ensemble est une caractéristique d’un ensemble, et que la définition d’un ensemble dans le langage doit avoir été faite en C, je parie que le test par s est plus rapide que celui qu’on peut faire avec les instructions Python qu’on est autrement obligé d’écrire.


J’ai ensuite encore trouvé d’autres solutions, mais l’algorithme de wiztricks est le meilleur et rend toutes mes solutions périmées.

Je suis parti du code de Isabella83 pour montrer progressivement comment il fallait le corriger pour qu’il marche puis l’améliorer, et ce faisant je n’ai pas cherché une solution aussi directe et élégante que celle de wiztricks




@ wiztricks



Ébouriffante “astuce“. Chapeau.

Ce n’est en fait pas une astuce, mais une simple constatation logique: quelle que soit la répétitivité des occurences dans les k premiers couples, seule la répétition de l’occurence du k-ième comme occurence des suivants peut faire étendre ListeRetour au delà du k-ième élément.

Cette “astuce“, je vais la retenir !
wiztricks: anagramme de wiz’s trick !




Cependant je n’ai pas pu m’empêcher de condenser. Au passage, j’itère k plutôt que de faire des append() , ce doit être plus performant:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
def occurence(li,k):
    k = min(k,len(li))
    last = li[k-1][1] # l'occurence du k-ieme (ou dernier si k==len(li) )
    for lettre,freq in li[k:]: # si k==len(li) alors li[k:] existe et vaut []
        if freq!=last:  break
        k+=1
    return [ lettre for lettre,_ in li[0:k] ]
 
Liste=  [("A",4),("B",3),("J", 3) , ("C",2),("D",2),("E",2),("F",2),("G",1),("H",1),("D",1)]
print '  ',[str(c[1]) for c in Liste] # pour suivre les resultats
for u in xrange(13):
    print str(u).rjust(2),occurence(Liste, u)

['4', '3', '3', '2', '2', '2', '2', '1', '1', '1']
0 []
1 ['A']
2 ['A', 'B', 'J']
3 ['A', 'B', 'J']
4 ['A', 'B', 'J', 'C', 'D', 'E', 'F']
5 ['A', 'B', 'J', 'C', 'D', 'E', 'F']
6 ['A', 'B', 'J', 'C', 'D', 'E', 'F']
7 ['A', 'B', 'J', 'C', 'D', 'E', 'F']
8 ['A', 'B', 'J', 'C', 'D', 'E', 'F', 'G', 'H', 'D']
9 ['A', 'B', 'J', 'C', 'D', 'E', 'F', 'G', 'H', 'D']
10 ['A', 'B', 'J', 'C', 'D', 'E', 'F', 'G', 'H', 'D']
11 ['A', 'B', 'J', 'C', 'D', 'E', 'F', 'G', 'H', 'D']
12 ['A', 'B', 'J', 'C', 'D', 'E', 'F', 'G', 'H', 'D']