module td_1a.construction_classique

Short summary

module ensae_teaching_cs.td_1a.construction_classique

Quelques constructions classiques pour éviter de recoder des variantes d’algorithmes. classiques.

source on GitHub

Functions

function truncated documentation
compte compte le nombre d’occurrences de chaque élément d’une liste
construit_matrice_carree cette construit une matrice carrée remplie de zéro sous la forme d’une liste de listes
enumerate_permutations énumère les permutations d’un ensemble de façon non récursive
enumerate_permutations_recursive énumère les permutations d’un ensemble de façon récursive
integrale calcule l’intégrale d’une fonction avec la méthode de Rienmann
mat2text convertit une matrice en une chaîne de caractères, réciproque de la fonction :func:
mat2vect convertit une matrice en un tableau à une seule dimension, réciproque de la fonction :func:
minindex Retourne l’index du minimum et le minimum.
recherche Retourne l’index d’un élément ou -1 si non trouvé
recherche_dichotomique Effectue une recherche dichotomique.
somme calcule la somme des éléments d’un tableau
text2mat convertit une chaîne de caractères en une matrice ( = liste de listes), réciproque de la fonction :func:
triindex trie une liste, retourne la liste triée et les positions initiales
vect2mat convertit un tableau à une dimension en une matrice, réciproque de la fonction :func:

Documentation

Quelques constructions classiques pour éviter de recoder des variantes d’algorithmes. classiques.

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.compte(li)[source]

compte le nombre d’occurrences de chaque élément d’une liste

Paramètres:li – tableau
Retourne:dictionnaire

comptage

On souhaite ici compter le nombre d’occurrences de chaque élément d’un tableau. Par exemple, on pourrait connaître par ce moyen la popularité d’un mot dans un discours politique ou l’étendue du vocabulaire utilisé. L’exemple suivant compte les mots d’une liste de mots.

li = ["un", "deux", "un", "trois"]
d  = { }
for l in li :
    if l not in d : d [l] = 1
    else : d [l] += 1
print (d)   # affiche {'un': 2, 'trois': 1, 'deux': 1}

La structure la plus appropriée ici est un dictionnaire puisqu’on cherche à associer une valeur à un élément d’une liste qui peut être de tout type. Si la liste contient des éléments de type modifiable comme une liste, il faudrait convertir ceux-ci en un type immuable comme une chaîne de caractères. L’exemple suivant illustre ce cas en comptant les occurrences des lignes d’une matrice.

mat = [ [1,1,1], [2,2,2], [1,1,1]]
d  = { }
for l in mat :
    k = str (l)    # k = tuple (l) lorsque cela est possible
    if k not in d : d [k] = 1
    else : d [k] += 1
print (d)   # affiche {'[1, 1, 1]': 2, '[2, 2, 2]': 1}

Les listes ne peuvent pas être les clés du dictionnaire : Why Lists Can’t Be Dictionary Keys.

On peut également vouloir non pas compter le nombre d’occurrence mais mémoriser les positions des éléments tous identiques. On doit utiliser un dictionnaire de listes :

li = ["un", "deux", "un", "trois"]
d  = { }
for i,v in enumerate (li) :
    if v not in d : d [v] = [ i ]
    else : d [v].append (i)
print (d)   # affiche {'un': [0, 2], 'trois': [3], 'deux': [1]}

S’il suffit juste compter, l’écriture la plus simple est :

for x in li : r[x] = r.get(x,0)+1

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.construit_matrice_carree(n)[source]

cette construit une matrice carrée remplie de zéro sous la forme d’une liste de listes

Paramètres:n – dimension de la matrice carrée

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.enumerate_permutations(ensemble)[source]

énumère les permutations d’un ensemble de façon non récursive

Paramètres:ensemble – ensemble à permuter
Retourne:itérateur sur les permutations

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.enumerate_permutations_recursive(ensemble)[source]

énumère les permutations d’un ensemble de façon récursive

Paramètres:ensemble – ensemble à permuter
Retourne:itérateur sur les permutations

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.integrale(fonction, a, b, n)[source]

calcule l’intégrale d’une fonction avec la méthode de Rienmann

Paramètres:
  • fonction – fonction
  • a – borne inférieure de l’intervalle
  • b – borne supérieure de l’intervalle
  • n – nombre de division de l’intervalle
Retourne:

valeur

fonction comme paramètre

Une fonction peut aussi recevoir en paramètre une autre fonction. L’exemple suivant inclut la fonction calcul_n_valeur qui prend comme paramètres l et f. Cette fonction calcule pour toutes les valeurs x de la liste l la valeur f(x). fonction_carre ou fonction_cube sont passées en paramètres à la fonction calcul_n_valeur qui les exécute.

def fonction_carre(x) : return x*x def fonction_cube (x) : return x*x*x

def calcul_n_valeur (l,f):
res = [ f(i) for i in l ] return res

l = [0,1,2,3] print l # affiche [0, 1, 2, 3]

l1 = calcul_n_valeur (l, fonction_carre) print l1 # affiche [0, 1, 4, 9]

l2 = calcul_n_valeur (l, fonction_cube) print l2 # affiche [0, 1, 8, 27]

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.mat2text(mat, sep_row='\n', sep_col='\t')[source]

convertit une matrice en une chaîne de caractères, réciproque de la fonction text2mat

Paramètres:
  • mat – matrice à convertir (liste de listes)
  • sep_row – séparation de ligne
  • sep_col – séparateur de colonnes
Retourne:

liste de liste

conversion d’une matrice en chaîne de caractères

mat     = [['case11', 'case12', 'case13'], ['case21', 'case22', 'case23']]
ligne   = [ ";".join (l) for l in mat ]     # colonnes
s       = "|".join (ligne)                  # lignes

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.mat2vect(mat)[source]

convertit une matrice en un tableau à une seule dimension, réciproque de la fonction vect2mat

Paramètres:mat – matrice
Retourne:liste

conversion d’une matrice en un vecteur

Dans un langage comme le C++, il arrive fréquemment qu’une matrice ne soit pas représentée par une liste de listes mais par une seule liste car cette représentation est plus efficace. Il faut donc convertir un indice en deux indices ligne et colonne. Il faut bien sûr que le nombre de colonnes sur chaque ligne soit constant. Le premier programme convertit une liste de listes en une seule liste.

mat = [[0,1,2],[3,4,5]]
lin = [ i * len (mat [i]) + j \
            for i in range (0, len (mat)) \
            for j in range (0, len (mat [i])) ]

Vous pouvez aussi utiliser des fonctions telles reduce.

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

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.minindex(li)[source]

Retourne l’index du minimum et le minimum.

Paramètres:li – liste
Retourne:tuple (minimum,position)

minimum avec position

La fonction min retourne le minium d’un tableau mais pas sa position. Le premier réflexe est alors de recoder le parcours de la liste tout en conservant la position du minimum.

li = [ 0, 434, 43, 6436, 5 ]
m  = 0
for i in range (0, len (li)) :
    if li [m] < li [i] : m = i

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

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

La fonction min choisit l’élément minimum d’un tableau dont les éléments sont des couples (élément du premier tableau, sa position). Le minimum est choisi en comparant les éléments, et la position départegera les exaequo.

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.recherche(li, c)[source]

Retourne l’index d’un élément ou -1 si non trouvé

Paramètres:
  • li – liste
  • c – élément à trouver
Retourne:

position

recherche avec index

Lorsqu’on cherche un élément dans un tableau, on cherche plus souvent sa position que le fait que le tableau contient cet élément.

def recherche (li, c) :
    for i,v in enumerate (li) :
        if v == c : return i
    return -1
li = [ 45, 32, 43, 56 ]
print (recherche (li, 43))  # affiche 2

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

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

Lorsque l’élément n’y est pas, on retourne souvent la position -1 qui ne peut être prise par aucun élément :

if c in li : return li.index(c)
else: return -1

Même si ce bout de code parcourt deux fois le tableau (une fois déterminer sa présence, une seconde fois pour sa position), ce code est souvent plus rapide que la première version et la probabilité d’y faire une erreur plus faible.

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.recherche_dichotomique(li, c)[source]

Effectue une recherche dichotomique.

Paramètres:
  • li – tableau
  • c – élément à chercher
Retourne:

position

recherche dichotomique

La recherche dichotomique est plus rapide qu’une recherche classique mais elle suppose que celle-ci s’effectue dans un ensemble trié. L’idée est de couper en deux l’intervalle de recherche à chaque itération. Comme l’ensemble est trié, en comparant l’élément cherché à l’élément central, on peut éliminer une partie de l’ensemble : la moitié inférieure ou supérieure.

def recherche_dichotomique (li, c) :
    a,b = 0, len (li)-1
    while a <= b :
        m = (a+b)/2
        if   c == li [m] : return m
        elif c <  li [m] : b = m-1   # partie supérieure éliminée
        else             : a = m+1   # partie inférieure éliminée
    return -1  # élément non trouvé

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.somme(li)[source]

calcule la somme des éléments d’un tableau

Paramètres:li – tableau
Retourne:somme

calcul d’une somme

Le calcul d’une somme fait toujours intervenir une boucle car le langage Python ne peut faire des additions qu’avec deux nombres. Le schéma est toujours le même : initialisation et boucle.

li = [ 0, 434, 43, 6456 ]
s  = 0                       # initialisation
for l in li :                # boucle
    s += l                   # addition

Ce code est équivalent à la fonction sum. Dans ce cas où la somme intègre le résultat d’une fonction et non les éléments d’une liste, il faudrait écrire :

def fonction (x) : return x*x
s  = 0
for l in li : s += fonction (l)

Et ces deux lignes pourraient être résumées en une seule grâce à l’une de ces instructions :

s = sum ( [fonction (l) for l in li] )
s = sum ( fonction (l) for l in li )
s = sum ( map (fonction, li) )

L’avantage des deux dernières instructions est qu’elles évitent la création d’une liste intermédiaire, c’est un point à prendre en compte si la liste sur laquelle opère la somme est volumineuse.

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.text2mat(s, sep_row='\n', sep_col='\t')[source]

convertit une chaîne de caractères en une matrice ( = liste de listes), réciproque de la fonction mat2text

Paramètres:
  • s – texte à convertir
  • sep_row – séparation de ligne
  • sep_col – séparateur de colonnes
Retourne:

liste de liste

conversion d’une chaîne de caractère en matrice

Les quelques lignes qui suivent permettent de décomposer une chaîne de caractères en matrice. Chaque ligne et chaque colonne sont séparées par des séparateurs différents. Ce procédé intervient souvent lorsqu’on récupère des informations depuis un fichier texte lui-même provenant d’un tableur.

s       = "case11;case12;case13|case21;case22;case23"
# décomposition en matrice
ligne   = s.split ("|")                     # lignes
mat     = [ l.split (";") for l in ligne ]  # colonnes

Comme cette opération est très fréquente lorsqu’on travaille avec les données, on ne l’implémente plus soi-même. On préfère utiliser un module comme pandas qui est plus robuste et considère plus de cas. Pour écrire, utilise la méthode to_csv, pour lire, la fonction read_csv. On peut également directement enregistrer au format Excel read_excel et écrire dans ce même format to_excel.

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.triindex(li)[source]

trie une liste, retourne la liste triée et les positions initiales

Paramètres:li – tableau
Retourne:liste triée

tri, garder les positions initiales

Le tri est une opération fréquente. On n’a pas toujours le temps de programmer le tri le plus efficace comme un tri quicksort et un tri plus simple suffit la plupart du temps. Le tri suivant consiste à recherche le plus petit élément puis à échanger sa place avec le premier élément du tableau du tableau. On recommence la même procédure à partir de la seconde position, puis la troisième et ainsi de suite jusqu’à la fin du tableau.

for i in xrange (0, len (li)) :
    # recherche du minimum entre i et len (li) exclu
    pos = i
    for j in range (i+1, len (li)) :
        if li [j] < li [pos] : pos = j
    # échange
    ech      = li [pos]
    li [pos] = li [i]
    li [i]   = ech

La fonction sorted trie également une liste mais selon un algorithme plus efficace que celui-ci (voir Timsort). On est parfois amené à reprogrammer un tri parce qu’on veut conserver la position des éléments dans le tableau non trié. Cela arrive quand on souhaite trier un tableau et appliquer la même transformation à un second tableau. Il est toujours préférable de ne pas reprogrammer un tri (moins d’erreur). Il suffit d’applicer la même idée que pour la fonction minindex.

tab = ["zero", "un", "deux"]                       # tableau à trier
pos = sorted(  (t,i) for i,t in enumerate(tab)  )  # tableau de couples
print (pos)                # affiche [('deux', 2), ('un', 1), ('zero', 0)]

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

tab = ["zero", "un", "deux"]
tab_position = [ (t,i) for i,t in enumerate(tab) ]
tab_position.sort()
print(tab_position)

source on GitHub

ensae_teaching_cs.td_1a.construction_classique.vect2mat(vect, ncol)[source]

convertit un tableau à une dimension en une matrice, réciproque de la fonction mat2vect

Paramètres:
  • vect – vecteur
  • ncol – nombre de colonnes
Retourne:

matrice

conversion d’un vecteur en une matrice

Dans un langage comme le C++, il arrive fréquemment qu’une matrice ne soit pas représentée par une liste de listes mais par une seule liste car cette représentation est plus efficace. Il faut donc convertir un indice en deux indices ligne et colonne. Il faut bien sûr que le nombre de colonnes sur chaque ligne soit constant. Le premier programme convertit une liste de listes en une seule liste.

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

source on GitHub