Coverage for src/ensae_teaching_cs/td_1a/construction_classique.py: 97%
71 statements
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
1# -*- coding: utf-8 -*-
2"""
3@file
4@brief Quelques constructions classiques pour éviter de recoder des variantes d'algorithmes.
5classiques.
6"""
8from functools import reduce
11def recherche(li, c):
12 """
13 Retourne l'index d'un élément ou -1 si non trouvé.
15 @param li liste
16 @param c élément à trouver
17 @return position
19 .. exref::
20 :tag: Base
21 :title: recherche avec index
23 Lorsqu'on cherche un élément dans un tableau, on cherche plus souvent
24 sa position que le fait que le tableau contient cet élément.
26 .. runpython::
27 :showcode:
29 def recherche (li, c) :
30 for i,v in enumerate (li) :
31 if v == c:
32 return i
33 return -1
34 li = [45, 32, 43, 56]
35 print (recherche(li, 43)) # affiche 2
37 En python, il existe un fonction simple qui permet de faire ça :
39 ::
41 print(li.index(43)) # affiche 2
43 Lorsque l'élément n'y est pas, on retourne souvent la position ``-1``
44 qui ne peut être prise par aucun élément :
46 ::
48 if c in li: return li.index(c)
49 else: return -1
51 Même si ce bout de code parcourt deux fois le tableau (une fois déterminer
52 sa présence, une seconde fois pour sa position), ce code est souvent plus rapide
53 que la première version et la probabilité d'y faire une erreur plus faible.
54 """
55 if c in li:
56 return li.index(c)
57 else:
58 return -1
61def minindex(li):
62 """
63 Retourne l'index du minimum et le minimum.
65 @param li liste
66 @return tuple (minimum,position)
69 .. exref::
70 :tag: Base
71 :title: minimum avec position
73 La fonction `min <https://docs.python.org/3/library/functions.html#min>`_
74 retourne le minium d'un tableau mais pas sa position.
75 Le premier réflexe est alors de recoder le parcours de la liste
76 tout en conservant la position du minimum.
78 .. runpython::
79 :showcode:
81 li = [0, 434, 43, 6436, 5]
82 m = 0
83 for i in range (0, len(li)):
84 if li[m] < li[i]:
85 m = i
86 print(m)
88 Mais il existe une astuce pour obtenir la position sans avoir à le reprogrammer.
90 .. runpython::
91 :showcode:
93 li = [0, 434, 43, 6436, 5]
94 k = [(v,i) for i, v in enumerate(li)]
95 m = min(k)
96 print(m)
98 La fonction ``min`` choisit l'élément minimum d'un tableau dont les éléments sont des
99 couples (élément du premier tableau, sa position).
100 Le minimum est choisi en comparant les éléments, et la position
101 départegera les exaequo.
102 """
103 return min((v, i) for i, v in enumerate(li))
106def recherche_dichotomique(li, c):
107 """
108 Effectue une recherche dichotomique.
110 @param li tableau
111 @param c élément à chercher
112 @return position
114 .. exref::
115 :tag: Base
116 :title: recherche dichotomique
118 La `recherche dichotomique <http://fr.wikipedia.org/wiki/Dichotomie>`_
119 est plus rapide qu'une recherche classique mais elle
120 suppose que celle-ci s'effectue dans un ensemble trié.
121 L'idée est de couper en deux l'intervalle de recherche à chaque itération.
122 Comme l'ensemble est trié, en comparant l'élément cherché à l'élément central,
123 on peut éliminer une partie de l'ensemble : la moitié inférieure ou supérieure.
125 .. runpython::
126 :showcode:
128 def recherche_dichotomique(li, c) :
129 a, b = 0, len (li)-1
130 while a <= b :
131 m = (a + b)//2
132 if c == li[m]: return m
133 elif c < li[m]: b = m-1
134 else : a = m+1
135 return -1
137 print(recherche_dichotomique([0, 2, 5, 7, 8], 7))
138 """
139 a, b = 0, len(li) - 1
140 while a <= b:
141 m = (a + b) // 2
142 if c == li[m]:
143 return m
144 elif c < li[m]:
145 b = m - 1 # partie supérieure éliminée
146 else:
147 a = m + 1 # partie inférieure éliminée
148 return -1 # élément non trouvé
151def text2mat(s, sep_row="\n", sep_col="\t"):
152 """
153 Convertit une chaîne de caractères en une matrice ( = liste de listes),
154 réciproque de la fonction @see fn mat2text.
156 @param s texte à convertir
157 @param sep_row séparation de ligne
158 @param sep_col séparateur de colonnes
159 @return liste de liste
161 .. exref::
162 :tag: Base
163 :title: conversion d'une chaîne de caractère en matrice
165 Les quelques lignes qui suivent permettent de décomposer une chaîne de caractères
166 en matrice. Chaque ligne et chaque colonne sont séparées par des
167 séparateurs différents. Ce procédé intervient souvent lorsqu'on récupère des
168 informations depuis un fichier texte lui-même provenant d'un tableur.
170 .. runpython::
171 :showcode:
173 s = "case11;case12;case13|case21;case22;case23"
174 # décomposition en matrice
175 ligne = s.split ("|") # lignes
176 mat = [ l.split (";") for l in ligne ] # colonnes
178 print(mat)
180 Comme cette opération est très fréquente lorsqu'on travaille avec les données,
181 on ne l'implémente plus soi-même. On préfère utiliser un module comme
182 `pandas <http://pandas.pydata.org/>`_ qui est plus robuste et considère plus de cas.
183 Pour écrire, utilise la méthode `to_csv <http://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.to_csv.html>`_,
184 pour lire, la fonction
185 `read_csv <http://pandas.pydata.org/pandas-docs/stable/generated/pandas.io.parsers.read_csv.html>`_.
186 On peut également directement enregistrer au format Excel
187 `read_excel <http://pandas.pydata.org/pandas-docs/stable/generated/pandas.io.excel.read_excel.html>`_ et écrire dans ce même format
188 `to_excel <http://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.to_excel.html>`_.
189 """
190 ligne = s.split(sep_row) # lignes
191 mat = [li.split(sep_col) for li in ligne] # colonnes
192 return mat
195def mat2text(mat, sep_row="\n", sep_col="\t"):
196 """
197 Convertit une matrice en une chaîne de caractères,
198 réciproque de la fonction @see fn text2mat.
200 @param mat matrice à convertir (liste de listes)
201 @param sep_row séparation de ligne
202 @param sep_col séparateur de colonnes
203 @return liste de liste
205 .. exref::
206 :tag: Base
207 :title: conversion d'une matrice en chaîne de caractères
209 .. runpython::
210 :showcode:
212 mat = [['case11', 'case12', 'case13'], ['case21', 'case22', 'case23']]
213 ligne = [ ";".join (l) for l in mat ] # colonnes
214 s = "|".join (ligne) # lignes
216 print(s)
217 """
218 ligne = [";".join(lc) for lc in mat] # colonnes
219 s = "|".join(ligne) # lignes
220 return s
223def somme(li):
224 """
225 Calcule la somme des éléments d'un tableau.
227 @param li tableau
228 @return somme
230 .. exref::
231 :tag: Base
232 :title: calcul d'une somme
234 Le calcul d'une somme fait toujours intervenir une boucle car le langage
235 :epkg:`Python` ne peut faire des additions qu'avec deux nombres.
236 Le schéma est toujours le même : initialisation et boucle.
238 .. runpython::
239 :showcode:
241 li = [0, 434, 43, 6456]
242 s = 0 # initialisation
243 for l in li : # boucle
244 s += l # addition
245 print(s)
247 Ce code est équivalent à la fonction `sum <https://docs.python.org/3/library/functions.html#sum>`_.
248 Dans ce cas où la somme intègre le résultat d'une fonction (au sens mathématique)
249 et non les éléments d'une liste, il faudrait écrire :
251 .. runpython::
252 :showcode:
254 def fonction(x):
255 return x
257 li = [0, 434, 43, 6456]
258 s = 0
259 for l in li:
260 s += fonction (l)
261 print(s)
263 Et ces deux lignes pourraient être résumées en une seule grâce
264 à l'une de ces instructions :
266 .. runpython::
267 :showcode:
269 def fonction(x):
270 return x
272 li = [0, 434, 43, 6456]
273 s1 = sum([fonction(l) for l in li])
274 s2 = sum(fonction(l) for l in li)
275 s3 = sum(map(fonction, li))
276 print(s1, s2, s3)
278 L'avantage des deux dernières instructions est qu'elles évitent
279 la création d'une liste intermédiaire,
280 c'est un point à prendre en compte si la liste sur laquelle opère la
281 somme est volumineuse.
282 """
283 return sum(li)
286def triindex(li):
287 """
288 Trie une liste, retourne la liste triée et les positions initiales.
290 @param li tableau
291 @return liste triée
293 .. exref::
294 :tag: Base
295 :title: tri, garder les positions initiales
297 Le tri est une opération fréquente. On n'a pas toujours le temps de programmer
298 le tri le plus efficace comme un tri `quicksort <http://fr.wikipedia.org/wiki/Tri_rapide>`_
299 et un tri plus simple suffit la plupart du temps.
300 Le tri suivant consiste à recherche le plus petit élément puis à
301 échanger sa place avec le premier élément du tableau du tableau.
302 On recommence la même procédure à partir de la seconde position,
303 puis la troisième et ainsi de suite jusqu'à la fin du tableau.
305 .. runpython::
306 :showcode:
308 li = [5, 6, 4, 3, 8, 2]
310 for i in range (0, len (li)) :
311 # recherche du minimum entre i et len (li) exclu
312 pos = i
313 for j in range (i+1, len (li)) :
314 if li [j] < li [pos] : pos = j
315 # échange
316 ech = li [pos]
317 li [pos] = li [i]
318 li [i] = ech
320 print(li)
322 La fonction `sorted <https://docs.python.org/3/library/functions.html#sorted>`_
323 trie également une liste mais selon un algorithme plus efficace
324 que celui-ci (voir `Timsort <http://en.wikipedia.org/wiki/Timsort>`_).
325 On est parfois amené à reprogrammer un tri parce qu'on veut conserver la position des éléments
326 dans le tableau non trié.
327 Cela arrive quand on souhaite trier un tableau et appliquer la même transformation à un second
328 tableau.
329 Il est toujours préférable de ne pas reprogrammer un tri (moins d'erreur).
330 Il suffit d'applicer la même idée que pour la fonction @see fn minindex.
332 .. runpython::
333 :showcode:
335 tab = ["zero", "un", "deux"] # tableau à trier
336 pos = sorted( (t,i) for i,t in enumerate(tab) ) # tableau de couples
337 print (pos) # affiche [('deux', 2), ('un', 1), ('zero', 0)]
339 Si cette écriture est trop succincte, on peut la décomposer en :
341 .. runpython::
342 :showcode:
344 tab = ["zero", "un", "deux"]
345 tab_position = [(t,i) for i,t in enumerate(tab)]
346 tab_position.sort()
347 print(tab_position)
348 """
349 return sorted((t, i) for i, t in enumerate(li))
352def compte(li):
353 """
354 Compte le nombre d'occurrences de chaque élément d'une liste.
356 @param li tableau
357 @return dictionnaire
359 .. exref::
360 :tag: Base
361 :title: comptage
363 On souhaite ici compter le nombre d'occurrences de chaque élément d'un tableau.
364 Par exemple, on pourrait connaître par ce moyen la popularité d'un mot dans un discours
365 politique ou l'étendue du vocabulaire utilisé.
366 L'exemple suivant compte les mots d'une liste de mots.
368 .. runpython::
369 :showcode:
371 li = ["un", "deux", "un", "trois"]
372 d = { }
373 for l in li:
374 if l not in d:
375 d[l] = 1
376 else:
377 d[l] += 1
378 print(d) # affiche {'un': 2, 'trois': 1, 'deux': 1}
380 La structure la plus appropriée ici est un dictionnaire puisqu'on cherche
381 à associer une valeur à un élément d'une liste qui peut être de tout type.
382 Si la liste contient des éléments de type modifiable comme une liste,
383 il faudrait convertir ceux-ci en un type immuable comme une chaîne de caractères.
384 L'exemple suivant illustre ce cas en comptant les occurrences des lignes d'une matrice.
386 .. runpython::
387 :showcode:
389 mat = [ [1,1,1], [2,2,2], [1,1,1]]
390 d = {}
391 for l in mat:
392 k = str(l) # k = tuple (l) lorsque cela est possible
393 if k not in d:
394 d[k] = 1
395 else:
396 d[k] += 1
397 print(d) # affiche {'[1, 1, 1]': 2, '[2, 2, 2]': 1}
399 Les listes ne peuvent pas être les clés du dictionnaire :
400 `Why Lists Can't Be Dictionary Keys <https://wiki.python.org/moin/DictionaryKeys>`_.
402 On peut également vouloir non pas compter le nombre d'occurrence mais mémoriser les
403 positions des éléments tous identiques. On doit utiliser un dictionnaire de listes :
405 .. runpython::
406 :showcode:
408 li = ["un", "deux", "un", "trois"]
409 d = { }
410 for i, v in enumerate(li):
411 if v not in d:
412 d[v] = [i]
413 else:
414 d[v].append(i)
415 print(d) # affiche {'un': [0, 2], 'trois': [3], 'deux': [1]}
417 S'il suffit juste de compter, l'écriture la plus simple est :
419 .. runpython::
420 :showcode:
422 r = {}
423 li = ["un", "deux", "un", "trois"]
424 for x in li:
425 r[x] = r.get(x,0) + 1
426 print(r)
427 """
428 r = {}
429 for x in li:
430 r[x] = r.get(x, 0) + 1
431 return r
434def mat2vect(mat):
435 """
436 Convertit une matrice en un tableau à une seule dimension,
437 réciproque de la fonction @see fn vect2mat.
439 @param mat matrice
440 @return liste
442 .. exref::
443 :tag: Base
444 :title: conversion d'une matrice en un vecteur
446 Dans un langage comme le *C++*, il arrive fréquemment qu'une matrice ne soit pas
447 représentée par une liste de listes mais par une seule liste car cette représentation
448 est plus efficace. Il faut donc convertir un indice en deux indices ligne et colonne.
449 Il faut bien sûr que le nombre de colonnes sur chaque ligne soit constant.
450 Le premier programme convertit une liste de listes en une seule liste.
452 .. runpython::
453 :showcode:
455 mat = [[0,1,2],[3,4,5]]
456 lin = [ i * len (mat [i]) + j \\
457 for i in range (0, len (mat)) \\
458 for j in range (0, len (mat [i])) ]
459 print(lin)
461 Vous pouvez aussi utiliser des fonctions telles que
462 `reduce <https://docs.python.org/3/library/functools.html?highlight=reduce#module-functools>`_.
464 .. runpython::
465 :showcode:
467 from functools import reduce
468 mat = [[0,1,2], [3,4,5]]
469 lin = reduce(lambda x,y: x+y, mat)
470 print(lin)
471 """
472 return reduce(lambda x, y: x + y, mat)
475def vect2mat(vect, ncol):
476 """
477 Convertit un tableau à une dimension en une matrice,
478 réciproque de la fonction @see fn mat2vect.
480 @param vect vecteur
481 @param ncol nombre de colonnes
482 @return matrice
484 .. exref::
485 :tag: Base
486 :title: conversion d'un vecteur en une matrice
488 Dans un langage comme le *C++*, il arrive fréquemment qu'une matrice ne soit pas
489 représentée par une liste de listes mais par une seule liste car cette représentation
490 est plus efficace. Il faut donc convertir un indice en deux indices ligne et colonne.
491 Il faut bien sûr que le nombre de colonnes sur chaque ligne soit constant.
492 Le premier programme convertit une liste de listes en une seule liste.
494 .. runpython::
495 :showcode:
497 ncol = 2
498 vect = [0, 1, 2, 3, 4, 5]
499 mat = [vect[i*ncol: (i+1)*ncol] for i in range(0,len(vect)//ncol)]
500 print(mat)
502 """
503 return [vect[i * ncol: (i + 1) * ncol]
504 for i in range(0, len(vect) // ncol)]
507def integrale(fonction, a, b, n):
508 """
509 Calcule l'intégrale d'une fonction avec la
510 `méthode de Rienmann <https://fr.wikipedia.org/wiki/Somme_de_Riemann>`_.
512 @param fonction fonction
513 @param a borne inférieure de l'intervalle
514 @param b borne supérieure de l'intervalle
515 @param n nombre de division de l'intervalle
516 @return valeur
518 .. exref::
519 :tag: Base
520 :title: fonction comme paramètre
522 Une fonction peut aussi recevoir en paramètre une autre fonction.
523 L'exemple suivant inclut la fonction ``calcul_n_valeur``
524 qui prend comme paramètres ``l`` et ``f``.
525 Cette fonction calcule pour toutes les valeurs ``x`` de la liste
526 ``l`` la valeur ``f(x)``.
527 ``fonction_carre`` ou ``fonction_cube`` sont passées en paramètres à la fonction
528 ``calcul_n_valeur`` qui les exécute.
530 .. runpython::
531 :showcode:
533 def fonction_carre(x):
534 return x*x
536 def fonction_cube(x):
537 return x*x*x
539 def calcul_n_valeur(l,f):
540 res = [f(i) for i in l]
541 return res
543 l = [0,1,2,3]
544 print(l) # affiche [0, 1, 2, 3]
546 l1 = calcul_n_valeur(l, fonction_carre)
547 print(l1) # affiche [0, 1, 4, 9]
549 l2 = calcul_n_valeur(l, fonction_cube)
550 print(l2) # affiche [0, 1, 8, 27]
551 """
552 h = (b - a) / n
553 return sum(fonction(a + h / 2 + h * i) for i in range(0, n)) * h
556def construit_matrice_carree(n):
557 """
558 Cette fonction construit une matrice carrée remplie de zéro
559 sous la forme d'une liste de listes.
561 @param n dimension de la matrice carrée
562 """
563 return [[0 for i in range(n)] for j in range(n)]
566def enumerate_permutations_recursive(ensemble):
567 """
568 Enumère les permutations d'un ensemble de façon récursive.
570 @param ensemble ensemble à permuter
571 @return itérateur sur les permutations
572 """
574 if len(ensemble) == 1:
575 yield ensemble
576 else:
577 for i in range(0, len(ensemble)):
578 ensemble[0], ensemble[i] = ensemble[i], ensemble[0]
579 per = enumerate_permutations_recursive(ensemble[1:])
580 for p in per:
581 yield [ensemble[0]] + p
582 ensemble[0], ensemble[i] = ensemble[i], ensemble[0]
585def enumerate_permutations(ensemble):
586 """
587 Enumère les permutations d'un ensemble de façon non récursive.
589 @param ensemble ensemble à permuter
590 @return itérateur sur les permutations
591 """
592 if len(ensemble) == 1:
593 yield ensemble
594 else:
595 position = list(range(len(ensemble)))
596 while position[0] < len(ensemble):
598 memo = []
599 for i, p in enumerate(position):
600 ensemble[i], ensemble[p] = ensemble[p], ensemble[i]
601 memo.append((i, p))
602 yield ensemble.copy()
603 for i, p in reversed(memo):
604 ensemble[i], ensemble[p] = ensemble[p], ensemble[i]
606 last = len(position) - 1
607 position[last] += 1
608 while last > 0 and position[last] >= len(position):
609 position[last - 1] += 1
610 position[last] = last
611 last -= 1