Coverage for src/teachpyx/examples/construction

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

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 :lid: l-ex-comptage

365

366 On souhaite ici compter le nombre d'occurrences de chaque élément d'un tableau.

367 Par exemple, on pourrait connaître par ce moyen la popularité d'un mot dans un discours

368 politique ou l'étendue du vocabulaire utilisé.

369 L'exemple suivant compte les mots d'une liste de mots.

370

371 .. runpython::

372 :showcode:

373

374 li = ["un", "deux", "un", "trois"]

375 d = { }

376 for l in li:

377 if l not in d:

378 d[l] = 1

379 else:

380 d[l] += 1

381 print(d) # affiche {'un': 2, 'trois': 1, 'deux': 1}

382

383 La structure la plus appropriée ici est un dictionnaire puisqu'on cherche

384 à associer une valeur à un élément d'une liste qui peut être de tout type.

385 Si la liste contient des éléments de type modifiable comme une liste,

386 il faudrait convertir ceux-ci en un type immuable comme une chaîne de caractères.

387 L'exemple suivant illustre ce cas en comptant les occurrences des lignes d'une matrice.

388

389 .. runpython::

390 :showcode:

391

392 mat = [ [1,1,1], [2,2,2], [1,1,1]]

393 d = {}

394 for l in mat:

395 k = str(l) # k = tuple (l) lorsque cela est possible

396 if k not in d:

397 d[k] = 1

398 else:

399 d[k] += 1

400 print(d) # affiche {'[1, 1, 1]': 2, '[2, 2, 2]': 1}

401

402 Les listes ne peuvent pas être les clés du dictionnaire :

403 `Why Lists Can't Be Dictionary Keys <https://wiki.python.org/moin/DictionaryKeys>`_.

404

405 On peut également vouloir non pas compter le nombre d'occurrence mais mémoriser les

406 positions des éléments tous identiques. On doit utiliser un dictionnaire de listes :

407

408 .. runpython::

409 :showcode:

410

411 li = ["un", "deux", "un", "trois"]

412 d = { }

413 for i, v in enumerate(li):

414 if v not in d:

415 d[v] = [i]

416 else:

417 d[v].append(i)

418 print(d) # affiche {'un': [0, 2], 'trois': [3], 'deux': [1]}

419

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

421

422 .. runpython::

423 :showcode:

424

425 r = {}

426 li = ["un", "deux", "un", "trois"]

427 for x in li:

428 r[x] = r.get(x,0) + 1

429 print(r)

430 """

431 r = {}

432 for x in li:

433 r[x] = r.get(x, 0) + 1

434 return r

435

436

437def mat2vect(mat):

438 """

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

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

441

442 @param mat matrice

443 @return liste

444

445 .. exref::

446 :tag: Base

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

448

449 Dans un langage comme le *C++*, il arrive fréquemment qu'une matrice ne soit pas

450 représentée par une liste de listes mais par une seule liste car cette représentation

451 est plus efficace. Il faut donc convertir un indice en deux indices ligne et colonne.

452 Il faut bien sûr que le nombre de colonnes sur chaque ligne soit constant.

453 Le premier programme convertit une liste de listes en une seule liste.

454

455 .. runpython::

456 :showcode:

457

458 mat = [[0,1,2],[3,4,5]]

459 lin = [ i * len (mat [i]) + j \\

460 for i in range (0, len (mat)) \\

461 for j in range (0, len (mat [i])) ]

462 print(lin)

463

464 Vous pouvez aussi utiliser des fonctions telles que

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

466

467 .. runpython::

468 :showcode:

469

470 from functools import reduce

471 mat = [[0,1,2], [3,4,5]]

472 lin = reduce(lambda x,y: x+y, mat)

473 print(lin)

474 """

475 return reduce(lambda x, y: x + y, mat)

476

477

478def vect2mat(vect, ncol):

479 """

480 Convertit un tableau à une dimension en une matrice,

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

482

483 @param vect vecteur

484 @param ncol nombre de colonnes

485 @return matrice

486

487 .. exref::

488 :tag: Base

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

490

491 Dans un langage comme le *C++*, il arrive fréquemment qu'une matrice ne soit pas

492 représentée par une liste de listes mais par une seule liste car cette représentation

493 est plus efficace. Il faut donc convertir un indice en deux indices ligne et colonne.

494 Il faut bien sûr que le nombre de colonnes sur chaque ligne soit constant.

495 Le premier programme convertit une liste de listes en une seule liste.

496

497 .. runpython::

498 :showcode:

499

500 ncol = 2

501 vect = [0, 1, 2, 3, 4, 5]

502 mat = [vect[i*ncol: (i+1)*ncol] for i in range(0,len(vect)//ncol)]

503 print(mat)

504

505 """

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

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

508

509

510def integrale(fonction, a, b, n):

511 """

512 Calcule l'intégrale d'une fonction avec la

513 `méthode de Rienmann <https://fr.wikipedia.org/wiki/Somme_de_Riemann>`_.

514

515 @param fonction fonction

516 @param a borne inférieure de l'intervalle

517 @param b borne supérieure de l'intervalle

518 @param n nombre de division de l'intervalle

519 @return valeur

520

521 .. exref::

522 :tag: Base

523 :title: fonction comme paramètre

524 :lid: paragraphe_fonction_variable

525

526 Une fonction peut aussi recevoir en paramètre une autre fonction.

527 L'exemple suivant inclut la fonction ``calcul_n_valeur``

528 qui prend comme paramètres ``l`` et ``f``.

529 Cette fonction calcule pour toutes les valeurs ``x`` de la liste

530 ``l`` la valeur ``f(x)``.

531 ``fonction_carre`` ou ``fonction_cube`` sont passées en paramètres à la fonction

532 ``calcul_n_valeur`` qui les exécute.

533

534 .. runpython::

535 :showcode:

536

537 def fonction_carre(x):

538 return x*x

539

540 def fonction_cube(x):

541 return x*x*x

542

543 def calcul_n_valeur(l,f):

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

545 return res

546

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

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

549

550 l1 = calcul_n_valeur(l, fonction_carre)

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

552

553 l2 = calcul_n_valeur(l, fonction_cube)

554 print(l2) # affiche [0, 1, 8, 27]

555 """

556 h = (b - a) / n

557 return sum(fonction(a + h / 2 + h * i) for i in range(0, n)) * h

558

559

560def construit_matrice_carree(n):

561 """

562 Cette fonction construit une matrice carrée remplie de zéro

563 sous la forme d'une liste de listes.

564

565 @param n dimension de la matrice carrée

566 """

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

568

569

570def enumerate_permutations_recursive(ensemble):

571 """

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

573

574 @param ensemble ensemble à permuter

575 @return itérateur sur les permutations

576 """

577

578 if len(ensemble) == 1:

579 yield ensemble

580 else:

581 for i in range(0, len(ensemble)): # pylint: disable=C0200

582 ensemble[0], ensemble[i] = ensemble[i], ensemble[0]

583 per = enumerate_permutations_recursive(ensemble[1:])

584 for p in per:

585 yield [ensemble[0]] + p

586 ensemble[0], ensemble[i] = ensemble[i], ensemble[0]

587

588

589def enumerate_permutations(ensemble):

590 """

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

592

593 @param ensemble ensemble à permuter

594 @return itérateur sur les permutations

595 """

596 if len(ensemble) == 1:

597 yield ensemble

598 else:

599 position = list(range(len(ensemble)))

600 while position[0] < len(ensemble):

601

602 memo = []

603 for i, p in enumerate(position):

604 ensemble[i], ensemble[p] = ensemble[p], ensemble[i]

605 memo.append((i, p))

606 yield ensemble.copy()

607 for i, p in reversed(memo):

608 ensemble[i], ensemble[p] = ensemble[p], ensemble[i]

609

610 last = len(position) - 1

611 position[last] += 1

612 while last > 0 and position[last] >= len(position):

613 position[last - 1] += 1

614 position[last] = last

615 last -= 1

Coverage for src/teachpyx/examples/construction_classique.py: 100%

71 statements