Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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:
49 return li.index(c)
50 else:
51 return -1
53 Même si ce bout de code parcourt deux fois le tableau (une fois déterminer
54 sa présence, une seconde fois pour sa position), ce code est souvent plus rapide
55 que la première version et la probabilité d'y faire une erreur plus faible.
56 """
57 if c in li:
58 return li.index(c)
59 else:
60 return -1
63def minindex(li):
64 """
65 Retourne l'index du minimum et le minimum.
67 @param li liste
68 @return tuple (minimum,position)
71 .. exref::
72 :tag: Base
73 :title: minimum avec position
75 La fonction `min <https://docs.python.org/3/library/functions.html#min>`_
76 retourne le minium d'un tableau mais pas sa position.
77 Le premier réflexe est alors de recoder le parcours de la liste
78 tout en conservant la position du minimum.
80 .. runpython::
81 :showcode:
83 li = [0, 434, 43, 6436, 5]
84 m = 0
85 for i in range (0, len(li)):
86 if li[m] < li[i]:
87 m = i
88 print(m)
90 Mais il existe une astuce pour obtenir la position sans avoir à le reprogrammer.
92 .. runpython::
93 :showcode:
95 li = [0, 434, 43, 6436, 5]
96 k = [(v,i) for i, v in enumerate(li)]
97 m = min(k)
98 print(m)
100 La fonction ``min`` choisit l'élément minimum d'un tableau dont les éléments sont des
101 couples (élément du premier tableau, sa position).
102 Le minimum est choisi en comparant les éléments, et la position
103 départegera les exaequo.
104 """
105 return min((v, i) for i, v in enumerate(li))
108def recherche_dichotomique(li, c):
109 """
110 Effectue une recherche dichotomique.
112 @param li tableau
113 @param c élément à chercher
114 @return position
116 .. exref::
117 :tag: Base
118 :title: recherche dichotomique
120 La `recherche dichotomique <http://fr.wikipedia.org/wiki/Dichotomie>`_
121 est plus rapide qu'une recherche classique mais elle
122 suppose que celle-ci s'effectue dans un ensemble trié.
123 L'idée est de couper en deux l'intervalle de recherche à chaque itération.
124 Comme l'ensemble est trié, en comparant l'élément cherché à l'élément central,
125 on peut éliminer une partie de l'ensemble : la moitié inférieure ou supérieure.
127 .. runpython::
128 :showcode:
130 def recherche_dichotomique(li, c) :
131 a, b = 0, len (li)-1
132 while a <= b :
133 m = (a + b)//2
134 if c == li[m]: return m
135 elif c < li[m]: b = m-1
136 else : a = m+1
137 return -1
139 print(recherche_dichotomique([0, 2, 5, 7, 8], 7))
140 """
141 a, b = 0, len(li) - 1
142 while a <= b:
143 m = (a + b) // 2
144 if c == li[m]:
145 return m
146 elif c < li[m]:
147 b = m - 1 # partie supérieure éliminée
148 else:
149 a = m + 1 # partie inférieure éliminée
150 return -1 # élément non trouvé
153def text2mat(s, sep_row="\n", sep_col="\t"):
154 """
155 Convertit une chaîne de caractères en une matrice ( = liste de listes),
156 réciproque de la fonction @see fn mat2text.
158 @param s texte à convertir
159 @param sep_row séparation de ligne
160 @param sep_col séparateur de colonnes
161 @return liste de liste
163 .. exref::
164 :tag: Base
165 :title: conversion d'une chaîne de caractère en matrice
167 Les quelques lignes qui suivent permettent de décomposer une chaîne de caractères
168 en matrice. Chaque ligne et chaque colonne sont séparées par des
169 séparateurs différents. Ce procédé intervient souvent lorsqu'on récupère des
170 informations depuis un fichier texte lui-même provenant d'un tableur.
172 .. runpython::
173 :showcode:
175 s = "case11;case12;case13|case21;case22;case23"
176 # décomposition en matrice
177 ligne = s.split ("|") # lignes
178 mat = [ l.split (";") for l in ligne ] # colonnes
180 print(mat)
182 Comme cette opération est très fréquente lorsqu'on travaille avec les données,
183 on ne l'implémente plus soi-même. On préfère utiliser un module comme
184 `pandas <http://pandas.pydata.org/>`_ qui est plus robuste et considère plus de cas.
185 Pour écrire, utilise la méthode `to_csv <http://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.to_csv.html>`_,
186 pour lire, la fonction
187 `read_csv <http://pandas.pydata.org/pandas-docs/stable/generated/pandas.io.parsers.read_csv.html>`_.
188 On peut également directement enregistrer au format Excel
189 `read_excel <http://pandas.pydata.org/pandas-docs/stable/generated/pandas.io.excel.read_excel.html>`_ et écrire dans ce même format
190 `to_excel <http://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.to_excel.html>`_.
191 """
192 ligne = s.split(sep_row) # lignes
193 mat = [el.split(sep_col) for el in ligne] # colonnes
194 return mat
197def mat2text(mat, sep_row="\n", sep_col="\t"):
198 """
199 Convertit une matrice en une chaîne de caractères,
200 réciproque de la fonction @see fn text2mat.
202 @param mat matrice à convertir (liste de listes)
203 @param sep_row séparation de ligne
204 @param sep_col séparateur de colonnes
205 @return liste de liste
207 .. exref::
208 :tag: Base
209 :title: conversion d'une matrice en chaîne de caractères
211 .. runpython::
212 :showcode:
214 mat = [['case11', 'case12', 'case13'], ['case21', 'case22', 'case23']]
215 ligne = [ ";".join (l) for l in mat ] # colonnes
216 s = "|".join (ligne) # lignes
218 print(s)
219 """
220 ligne = [";".join(li) for li in mat] # colonnes
221 s = "|".join(ligne) # lignes
222 return s
225def somme(li):
226 """
227 Calcule la somme des éléments d'un tableau.
229 @param li tableau
230 @return somme
232 .. exref::
233 :tag: Base
234 :title: calcul d'une somme
236 Le calcul d'une somme fait toujours intervenir une boucle car le langage
237 :epkg:`Python` ne peut faire des additions qu'avec deux nombres.
238 Le schéma est toujours le même : initialisation et boucle.
240 .. runpython::
241 :showcode:
243 li = [0, 434, 43, 6456]
244 s = 0 # initialisation
245 for l in li : # boucle
246 s += l # addition
247 print(s)
249 Ce code est équivalent à la fonction `sum <https://docs.python.org/3/library/functions.html#sum>`_.
250 Dans ce cas où la somme intègre le résultat d'une fonction (au sens mathématique)
251 et non les éléments d'une liste, il faudrait écrire :
253 .. runpython::
254 :showcode:
256 def fonction(x):
257 return x
259 li = [0, 434, 43, 6456]
260 s = 0
261 for l in li:
262 s += fonction (l)
263 print(s)
265 Et ces deux lignes pourraient être résumées en une seule grâce
266 à l'une de ces instructions :
268 .. runpython::
269 :showcode:
271 def fonction(x):
272 return x
274 li = [0, 434, 43, 6456]
275 s1 = sum([fonction(l) for l in li])
276 s2 = sum(fonction(l) for l in li)
277 s3 = sum(map(fonction, li))
278 print(s1, s2, s3)
280 L'avantage des deux dernières instructions est qu'elles évitent
281 la création d'une liste intermédiaire,
282 c'est un point à prendre en compte si la liste sur laquelle opère la
283 somme est volumineuse.
284 """
285 return sum(li)
288def triindex(li):
289 """
290 Trie une liste, retourne la liste triée et les positions initiales.
292 @param li tableau
293 @return liste triée
295 .. exref::
296 :tag: Base
297 :title: tri, garder les positions initiales
299 Le tri est une opération fréquente. On n'a pas toujours le temps de programmer
300 le tri le plus efficace comme un tri `quicksort <http://fr.wikipedia.org/wiki/Tri_rapide>`_
301 et un tri plus simple suffit la plupart du temps.
302 Le tri suivant consiste à recherche le plus petit élément puis à
303 échanger sa place avec le premier élément du tableau du tableau.
304 On recommence la même procédure à partir de la seconde position,
305 puis la troisième et ainsi de suite jusqu'à la fin du tableau.
307 .. runpython::
308 :showcode:
310 li = [5, 6, 4, 3, 8, 2]
312 for i in range (0, len (li)) :
313 # recherche du minimum entre i et len (li) exclu
314 pos = i
315 for j in range (i+1, len (li)) :
316 if li [j] < li [pos] : pos = j
317 # échange
318 ech = li [pos]
319 li [pos] = li [i]
320 li [i] = ech
322 print(li)
324 La fonction `sorted <https://docs.python.org/3/library/functions.html#sorted>`_
325 trie également une liste mais selon un algorithme plus efficace
326 que celui-ci (voir `Timsort <http://en.wikipedia.org/wiki/Timsort>`_).
327 On est parfois amené à reprogrammer un tri parce qu'on veut conserver la position des éléments
328 dans le tableau non trié.
329 Cela arrive quand on souhaite trier un tableau et appliquer la même transformation à un second
330 tableau.
331 Il est toujours préférable de ne pas reprogrammer un tri (moins d'erreur).
332 Il suffit d'applicer la même idée que pour la fonction @see fn minindex.
334 .. runpython::
335 :showcode:
337 tab = ["zero", "un", "deux"] # tableau à trier
338 pos = sorted( (t,i) for i,t in enumerate(tab) ) # tableau de couples
339 print (pos) # affiche [('deux', 2), ('un', 1), ('zero', 0)]
341 Si cette écriture est trop succincte, on peut la décomposer en :
343 .. runpython::
344 :showcode:
346 tab = ["zero", "un", "deux"]
347 tab_position = [(t,i) for i,t in enumerate(tab)]
348 tab_position.sort()
349 print(tab_position)
350 """
351 return sorted((t, i) for i, t in enumerate(li))
354def compte(li):
355 """
356 Compte le nombre d'occurrences de chaque élément d'une liste.
358 @param li tableau
359 @return dictionnaire
361 .. exref::
362 :tag: Base
363 :title: comptage
365 On souhaite ici compter le nombre d'occurrences de chaque élément d'un tableau.
366 Par exemple, on pourrait connaître par ce moyen la popularité d'un mot dans un discours
367 politique ou l'étendue du vocabulaire utilisé.
368 L'exemple suivant compte les mots d'une liste de mots.
370 .. runpython::
371 :showcode:
373 li = ["un", "deux", "un", "trois"]
374 d = { }
375 for l in li:
376 if l not in d:
377 d[l] = 1
378 else:
379 d[l] += 1
380 print(d) # affiche {'un': 2, 'trois': 1, 'deux': 1}
382 La structure la plus appropriée ici est un dictionnaire puisqu'on cherche
383 à associer une valeur à un élément d'une liste qui peut être de tout type.
384 Si la liste contient des éléments de type modifiable comme une liste,
385 il faudrait convertir ceux-ci en un type immuable comme une chaîne de caractères.
386 L'exemple suivant illustre ce cas en comptant les occurrences des lignes d'une matrice.
388 .. runpython::
389 :showcode:
391 mat = [ [1,1,1], [2,2,2], [1,1,1]]
392 d = {}
393 for l in mat:
394 k = str(l) # k = tuple (l) lorsque cela est possible
395 if k not in d:
396 d[k] = 1
397 else:
398 d[k] += 1
399 print(d) # affiche {'[1, 1, 1]': 2, '[2, 2, 2]': 1}
401 Les listes ne peuvent pas être les clés du dictionnaire :
402 `Why Lists Can't Be Dictionary Keys <https://wiki.python.org/moin/DictionaryKeys>`_.
404 On peut également vouloir non pas compter le nombre d'occurrence mais mémoriser les
405 positions des éléments tous identiques. On doit utiliser un dictionnaire de listes :
407 .. runpython::
408 :showcode:
410 li = ["un", "deux", "un", "trois"]
411 d = { }
412 for i, v in enumerate(li):
413 if v not in d:
414 d[v] = [i]
415 else:
416 d[v].append(i)
417 print(d) # affiche {'un': [0, 2], 'trois': [3], 'deux': [1]}
419 S'il suffit juste de compter, l'écriture la plus simple est :
421 .. runpython::
422 :showcode:
424 r = {}
425 li = ["un", "deux", "un", "trois"]
426 for x in li:
427 r[x] = r.get(x,0) + 1
428 print(r)
429 """
430 r = {}
431 for x in li:
432 r[x] = r.get(x, 0) + 1
433 return r
436def mat2vect(mat):
437 """
438 Convertit une matrice en un tableau à une seule dimension,
439 réciproque de la fonction @see fn vect2mat.
441 @param mat matrice
442 @return liste
444 .. exref::
445 :tag: Base
446 :title: conversion d'une matrice en un vecteur
448 Dans un langage comme le *C++*, il arrive fréquemment qu'une matrice ne soit pas
449 représentée par une liste de listes mais par une seule liste car cette représentation
450 est plus efficace. Il faut donc convertir un indice en deux indices ligne et colonne.
451 Il faut bien sûr que le nombre de colonnes sur chaque ligne soit constant.
452 Le premier programme convertit une liste de listes en une seule liste.
454 .. runpython::
455 :showcode:
457 mat = [[0,1,2],[3,4,5]]
458 lin = [ i * len (mat [i]) + j \\
459 for i in range (0, len (mat)) \\
460 for j in range (0, len (mat [i])) ]
461 print(lin)
463 Vous pouvez aussi utiliser des fonctions telles que
464 `reduce <https://docs.python.org/3/library/functools.html?highlight=reduce#module-functools>`_.
466 .. runpython::
467 :showcode:
469 from functools import reduce
470 mat = [[0,1,2], [3,4,5]]
471 lin = reduce(lambda x,y: x+y, mat)
472 print(lin)
473 """
474 return reduce(lambda x, y: x + y, mat)
477def vect2mat(vect, ncol):
478 """
479 Convertit un tableau à une dimension en une matrice,
480 réciproque de la fonction @see fn mat2vect.
482 @param vect vecteur
483 @param ncol nombre de colonnes
484 @return matrice
486 .. exref::
487 :tag: Base
488 :title: conversion d'un vecteur en une matrice
490 Dans un langage comme le *C++*, il arrive fréquemment qu'une matrice ne soit pas
491 représentée par une liste de listes mais par une seule liste car cette représentation
492 est plus efficace. Il faut donc convertir un indice en deux indices ligne et colonne.
493 Il faut bien sûr que le nombre de colonnes sur chaque ligne soit constant.
494 Le premier programme convertit une liste de listes en une seule liste.
496 .. runpython::
497 :showcode:
499 ncol = 2
500 vect = [0, 1, 2, 3, 4, 5]
501 mat = [vect[i*ncol: (i+1)*ncol] for i in range(0,len(vect)//ncol)]
502 print(mat)
504 """
505 return [vect[i * ncol: (i + 1) * ncol]
506 for i in range(0, len(vect) // ncol)]
509def integrale(fonction, a, b, n):
510 """
511 Calcule l'intégrale d'une fonction avec la
512 `méthode de Rienmann <https://fr.wikipedia.org/wiki/Somme_de_Riemann>`_.
514 @param fonction fonction
515 @param a borne inférieure de l'intervalle
516 @param b borne supérieure de l'intervalle
517 @param n nombre de division de l'intervalle
518 @return valeur
520 .. exref::
521 :tag: Base
522 :title: fonction comme paramètre
523 :lid: paragraphe_fonction_variable
525 Une fonction peut aussi recevoir en paramètre une autre fonction.
526 L'exemple suivant inclut la fonction ``calcul_n_valeur``
527 qui prend comme paramètres ``l`` et ``f``.
528 Cette fonction calcule pour toutes les valeurs ``x`` de la liste
529 ``l`` la valeur ``f(x)``.
530 ``fonction_carre`` ou ``fonction_cube`` sont passées en paramètres à la fonction
531 ``calcul_n_valeur`` qui les exécute.
533 .. runpython::
534 :showcode:
536 def fonction_carre(x):
537 return x*x
539 def fonction_cube(x):
540 return x*x*x
542 def calcul_n_valeur(l,f):
543 res = [f(i) for i in l]
544 return res
546 l = [0,1,2,3]
547 print(l) # affiche [0, 1, 2, 3]
549 l1 = calcul_n_valeur(l, fonction_carre)
550 print(l1) # affiche [0, 1, 4, 9]
552 l2 = calcul_n_valeur(l, fonction_cube)
553 print(l2) # affiche [0, 1, 8, 27]
554 """
555 h = (b - a) / n
556 return sum(fonction(a + h / 2 + h * i) for i in range(0, n)) * h
559def construit_matrice_carree(n):
560 """
561 Cette fonction construit une matrice carrée remplie de zéro
562 sous la forme d'une liste de listes.
564 @param n dimension de la matrice carrée
565 """
566 return [[0 for i in range(n)] for j in range(n)]
569def enumerate_permutations_recursive(ensemble):
570 """
571 Enumère les permutations d'un ensemble de façon récursive.
573 @param ensemble ensemble à permuter
574 @return itérateur sur les permutations
575 """
577 if len(ensemble) == 1:
578 yield ensemble
579 else:
580 for i in range(0, len(ensemble)): # pylint: disable=C0200
581 ensemble[0], ensemble[i] = ensemble[i], ensemble[0]
582 per = enumerate_permutations_recursive(ensemble[1:])
583 for p in per:
584 yield [ensemble[0]] + p
585 ensemble[0], ensemble[i] = ensemble[i], ensemble[0]
588def enumerate_permutations(ensemble):
589 """
590 Enumère les permutations d'un ensemble de façon non récursive.
592 @param ensemble ensemble à permuter
593 @return itérateur sur les permutations
594 """
595 if len(ensemble) == 1:
596 yield ensemble
597 else:
598 position = list(range(len(ensemble)))
599 while position[0] < len(ensemble):
601 memo = []
602 for i, p in enumerate(position):
603 ensemble[i], ensemble[p] = ensemble[p], ensemble[i]
604 memo.append((i, p))
605 yield ensemble.copy()
606 for i, p in reversed(memo):
607 ensemble[i], ensemble[p] = ensemble[p], ensemble[i]
609 last = len(position) - 1
610 position[last] += 1
611 while last > 0 and position[last] >= len(position):
612 position[last - 1] += 1
613 position[last] = last
614 last -= 1