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-01-27 05:44 +0100

1# -*- coding: utf-8 -*- 

2""" 

3@file 

4@brief Quelques constructions classiques pour éviter de recoder des variantes d'algorithmes. 

5classiques. 

6""" 

7 

8from functools import reduce 

9 

10 

11def recherche(li, c): 

12 """ 

13 Retourne l'index d'un élément ou -1 si non trouvé. 

14 

15 @param li liste 

16 @param c élément à trouver 

17 @return position 

18 

19 .. exref:: 

20 :tag: Base 

21 :title: recherche avec index 

22 

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. 

25 

26 .. runpython:: 

27 :showcode: 

28 

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 

36 

37 En python, il existe un fonction simple qui permet de faire ça : 

38 

39 :: 

40 

41 print(li.index(43)) # affiche 2 

42 

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 : 

45 

46 :: 

47 

48 if c in li: return li.index(c) 

49 else: return -1 

50 

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 

59 

60 

61def minindex(li): 

62 """ 

63 Retourne l'index du minimum et le minimum. 

64 

65 @param li liste 

66 @return tuple (minimum,position) 

67 

68 

69 .. exref:: 

70 :tag: Base 

71 :title: minimum avec position 

72 

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. 

77 

78 .. runpython:: 

79 :showcode: 

80 

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) 

87 

88 Mais il existe une astuce pour obtenir la position sans avoir à le reprogrammer. 

89 

90 .. runpython:: 

91 :showcode: 

92 

93 li = [0, 434, 43, 6436, 5] 

94 k = [(v,i) for i, v in enumerate(li)] 

95 m = min(k) 

96 print(m) 

97 

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

104 

105 

106def recherche_dichotomique(li, c): 

107 """ 

108 Effectue une recherche dichotomique. 

109 

110 @param li tableau 

111 @param c élément à chercher 

112 @return position 

113 

114 .. exref:: 

115 :tag: Base 

116 :title: recherche dichotomique 

117 

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. 

124 

125 .. runpython:: 

126 :showcode: 

127 

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 

136 

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é 

149 

150 

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. 

155 

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 

160 

161 .. exref:: 

162 :tag: Base 

163 :title: conversion d'une chaîne de caractère en matrice 

164 

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. 

169 

170 .. runpython:: 

171 :showcode: 

172 

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 

177 

178 print(mat) 

179 

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 

193 

194 

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. 

199 

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 

204 

205 .. exref:: 

206 :tag: Base 

207 :title: conversion d'une matrice en chaîne de caractères 

208 

209 .. runpython:: 

210 :showcode: 

211 

212 mat = [['case11', 'case12', 'case13'], ['case21', 'case22', 'case23']] 

213 ligne = [ ";".join (l) for l in mat ] # colonnes 

214 s = "|".join (ligne) # lignes 

215 

216 print(s) 

217 """ 

218 ligne = [";".join(lc) for lc in mat] # colonnes 

219 s = "|".join(ligne) # lignes 

220 return s 

221 

222 

223def somme(li): 

224 """ 

225 Calcule la somme des éléments d'un tableau. 

226 

227 @param li tableau 

228 @return somme 

229 

230 .. exref:: 

231 :tag: Base 

232 :title: calcul d'une somme 

233 

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. 

237 

238 .. runpython:: 

239 :showcode: 

240 

241 li = [0, 434, 43, 6456] 

242 s = 0 # initialisation 

243 for l in li : # boucle 

244 s += l # addition 

245 print(s) 

246 

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 : 

250 

251 .. runpython:: 

252 :showcode: 

253 

254 def fonction(x): 

255 return x 

256 

257 li = [0, 434, 43, 6456] 

258 s = 0 

259 for l in li: 

260 s += fonction (l) 

261 print(s) 

262 

263 Et ces deux lignes pourraient être résumées en une seule grâce 

264 à l'une de ces instructions : 

265 

266 .. runpython:: 

267 :showcode: 

268 

269 def fonction(x): 

270 return x 

271 

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) 

277 

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) 

284 

285 

286def triindex(li): 

287 """ 

288 Trie une liste, retourne la liste triée et les positions initiales. 

289 

290 @param li tableau 

291 @return liste triée 

292 

293 .. exref:: 

294 :tag: Base 

295 :title: tri, garder les positions initiales 

296 

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. 

304 

305 .. runpython:: 

306 :showcode: 

307 

308 li = [5, 6, 4, 3, 8, 2] 

309 

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 

319 

320 print(li) 

321 

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. 

331 

332 .. runpython:: 

333 :showcode: 

334 

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)] 

338 

339 Si cette écriture est trop succincte, on peut la décomposer en : 

340 

341 .. runpython:: 

342 :showcode: 

343 

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

350 

351 

352def compte(li): 

353 """ 

354 Compte le nombre d'occurrences de chaque élément d'une liste. 

355 

356 @param li tableau 

357 @return dictionnaire 

358 

359 .. exref:: 

360 :tag: Base 

361 :title: comptage 

362 

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. 

367 

368 .. runpython:: 

369 :showcode: 

370 

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} 

379 

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. 

385 

386 .. runpython:: 

387 :showcode: 

388 

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} 

398 

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

401 

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 : 

404 

405 .. runpython:: 

406 :showcode: 

407 

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]} 

416 

417 S'il suffit juste de compter, l'écriture la plus simple est : 

418 

419 .. runpython:: 

420 :showcode: 

421 

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 

432 

433 

434def mat2vect(mat): 

435 """ 

436 Convertit une matrice en un tableau à une seule dimension, 

437 réciproque de la fonction @see fn vect2mat. 

438 

439 @param mat matrice 

440 @return liste 

441 

442 .. exref:: 

443 :tag: Base 

444 :title: conversion d'une matrice en un vecteur 

445 

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. 

451 

452 .. runpython:: 

453 :showcode: 

454 

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) 

460 

461 Vous pouvez aussi utiliser des fonctions telles que 

462 `reduce <https://docs.python.org/3/library/functools.html?highlight=reduce#module-functools>`_. 

463 

464 .. runpython:: 

465 :showcode: 

466 

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) 

473 

474 

475def vect2mat(vect, ncol): 

476 """ 

477 Convertit un tableau à une dimension en une matrice, 

478 réciproque de la fonction @see fn mat2vect. 

479 

480 @param vect vecteur 

481 @param ncol nombre de colonnes 

482 @return matrice 

483 

484 .. exref:: 

485 :tag: Base 

486 :title: conversion d'un vecteur en une matrice 

487 

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. 

493 

494 .. runpython:: 

495 :showcode: 

496 

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) 

501 

502 """ 

503 return [vect[i * ncol: (i + 1) * ncol] 

504 for i in range(0, len(vect) // ncol)] 

505 

506 

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

511 

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 

517 

518 .. exref:: 

519 :tag: Base 

520 :title: fonction comme paramètre 

521 

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. 

529 

530 .. runpython:: 

531 :showcode: 

532 

533 def fonction_carre(x): 

534 return x*x 

535 

536 def fonction_cube(x): 

537 return x*x*x 

538 

539 def calcul_n_valeur(l,f): 

540 res = [f(i) for i in l] 

541 return res 

542 

543 l = [0,1,2,3] 

544 print(l) # affiche [0, 1, 2, 3] 

545 

546 l1 = calcul_n_valeur(l, fonction_carre) 

547 print(l1) # affiche [0, 1, 4, 9] 

548 

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 

554 

555 

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. 

560 

561 @param n dimension de la matrice carrée 

562 """ 

563 return [[0 for i in range(n)] for j in range(n)] 

564 

565 

566def enumerate_permutations_recursive(ensemble): 

567 """ 

568 Enumère les permutations d'un ensemble de façon récursive. 

569 

570 @param ensemble ensemble à permuter 

571 @return itérateur sur les permutations 

572 """ 

573 

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] 

583 

584 

585def enumerate_permutations(ensemble): 

586 """ 

587 Enumère les permutations d'un ensemble de façon non récursive. 

588 

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): 

597 

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] 

605 

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