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: 

49 return li.index(c) 

50 else: 

51 return -1 

52 

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 

61 

62 

63def minindex(li): 

64 """ 

65 Retourne l'index du minimum et le minimum. 

66 

67 @param li liste 

68 @return tuple (minimum,position) 

69 

70 

71 .. exref:: 

72 :tag: Base 

73 :title: minimum avec position 

74 

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. 

79 

80 .. runpython:: 

81 :showcode: 

82 

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) 

89 

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

91 

92 .. runpython:: 

93 :showcode: 

94 

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

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

97 m = min(k) 

98 print(m) 

99 

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

106 

107 

108def recherche_dichotomique(li, c): 

109 """ 

110 Effectue une recherche dichotomique. 

111 

112 @param li tableau 

113 @param c élément à chercher 

114 @return position 

115 

116 .. exref:: 

117 :tag: Base 

118 :title: recherche dichotomique 

119 

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. 

126 

127 .. runpython:: 

128 :showcode: 

129 

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 

138 

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é 

151 

152 

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. 

157 

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 

162 

163 .. exref:: 

164 :tag: Base 

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

166 

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. 

171 

172 .. runpython:: 

173 :showcode: 

174 

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 

179 

180 print(mat) 

181 

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 

195 

196 

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. 

201 

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 

206 

207 .. exref:: 

208 :tag: Base 

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

210 

211 .. runpython:: 

212 :showcode: 

213 

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

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

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

217 

218 print(s) 

219 """ 

220 ligne = [";".join(li) for li in mat] # colonnes 

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

222 return s 

223 

224 

225def somme(li): 

226 """ 

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

228 

229 @param li tableau 

230 @return somme 

231 

232 .. exref:: 

233 :tag: Base 

234 :title: calcul d'une somme 

235 

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. 

239 

240 .. runpython:: 

241 :showcode: 

242 

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

244 s = 0 # initialisation 

245 for l in li : # boucle 

246 s += l # addition 

247 print(s) 

248 

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 : 

252 

253 .. runpython:: 

254 :showcode: 

255 

256 def fonction(x): 

257 return x 

258 

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

260 s = 0 

261 for l in li: 

262 s += fonction (l) 

263 print(s) 

264 

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

266 à l'une de ces instructions : 

267 

268 .. runpython:: 

269 :showcode: 

270 

271 def fonction(x): 

272 return x 

273 

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) 

279 

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) 

286 

287 

288def triindex(li): 

289 """ 

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

291 

292 @param li tableau 

293 @return liste triée 

294 

295 .. exref:: 

296 :tag: Base 

297 :title: tri, garder les positions initiales 

298 

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. 

306 

307 .. runpython:: 

308 :showcode: 

309 

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

311 

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 

321 

322 print(li) 

323 

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. 

333 

334 .. runpython:: 

335 :showcode: 

336 

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

340 

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

342 

343 .. runpython:: 

344 :showcode: 

345 

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

352 

353 

354def compte(li): 

355 """ 

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

357 

358 @param li tableau 

359 @return dictionnaire 

360 

361 .. exref:: 

362 :tag: Base 

363 :title: comptage 

364 

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. 

369 

370 .. runpython:: 

371 :showcode: 

372 

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} 

381 

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. 

387 

388 .. runpython:: 

389 :showcode: 

390 

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} 

400 

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

403 

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 : 

406 

407 .. runpython:: 

408 :showcode: 

409 

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

418 

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

420 

421 .. runpython:: 

422 :showcode: 

423 

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 

434 

435 

436def mat2vect(mat): 

437 """ 

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

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

440 

441 @param mat matrice 

442 @return liste 

443 

444 .. exref:: 

445 :tag: Base 

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

447 

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. 

453 

454 .. runpython:: 

455 :showcode: 

456 

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) 

462 

463 Vous pouvez aussi utiliser des fonctions telles que 

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

465 

466 .. runpython:: 

467 :showcode: 

468 

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) 

475 

476 

477def vect2mat(vect, ncol): 

478 """ 

479 Convertit un tableau à une dimension en une matrice, 

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

481 

482 @param vect vecteur 

483 @param ncol nombre de colonnes 

484 @return matrice 

485 

486 .. exref:: 

487 :tag: Base 

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

489 

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. 

495 

496 .. runpython:: 

497 :showcode: 

498 

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) 

503 

504 """ 

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

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

507 

508 

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

513 

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 

519 

520 .. exref:: 

521 :tag: Base 

522 :title: fonction comme paramètre 

523 :lid: paragraphe_fonction_variable 

524 

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. 

532 

533 .. runpython:: 

534 :showcode: 

535 

536 def fonction_carre(x): 

537 return x*x 

538 

539 def fonction_cube(x): 

540 return x*x*x 

541 

542 def calcul_n_valeur(l,f): 

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

544 return res 

545 

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

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

548 

549 l1 = calcul_n_valeur(l, fonction_carre) 

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

551 

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 

557 

558 

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. 

563 

564 @param n dimension de la matrice carrée 

565 """ 

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

567 

568 

569def enumerate_permutations_recursive(ensemble): 

570 """ 

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

572 

573 @param ensemble ensemble à permuter 

574 @return itérateur sur les permutations 

575 """ 

576 

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] 

586 

587 

588def enumerate_permutations(ensemble): 

589 """ 

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

591 

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

600 

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] 

608 

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