Algorithmes en Python

Les programmes ci-dessous utilisent les listes de Python (programme : générer une liste en extension, par ajouts successifs ou en compréhension, la parcourir). En langage naturel, l'affectation s'écrit avec une flèche : « $L \leftarrow [1]$ » se lit « $L$ prend la valeur $[1]$ ».

7.1 Le triangle de Pascal

Une ligne à partir de la précédente. La ligne suivante commence par $1$, contient ensuite les sommes de deux nombres voisins de la ligne $L$, et finit par $1$ : c'est la relation de Pascal.

def ligne_suivante(L):
    M = [1]
    for k in range(1, len(L)):
        M.append(L[k-1] + L[k])
    M.append(1)
    return M

La même fonction s'écrit aussi avec une liste en compréhension : return [1] + [L[k-1] + L[k] for k in range(1, len(L))] + [1].

La ligne $n$. On part de la ligne $0$, qui vaut [1], et on applique $n$ fois la fonction.

def pascal(n):
    L = [1]
    for i in range(n):
        L = ligne_suivante(L)
    return L

>>> pascal(5)
[1, 5, 10, 10, 5, 1]
>>> sum(pascal(10))
1024

La seconde ligne vérifie la propriété de la leçon 6 : $\sum\limits_{k=0}^{10} \binom{10}{k} = 2^{10} = 1\,024$.

7.2 Les parties à 2 ou 3 éléments d'un ensemble

On représente un ensemble par la liste de ses éléments. Pour obtenir chaque partie une seule fois, on impose aux indices d'être rangés dans l'ordre croissant : $i < j$.

E = ['a', 'b', 'c', 'd', 'e']
n = len(E)
P2 = [[E[i], E[j]] for i in range(n) for j in range(i+1, n)]

>>> P2
[['a', 'b'], ['a', 'c'], ['a', 'd'], ['a', 'e'], ['b', 'c'], ['b', 'd'], ['b', 'e'], ['c', 'd'], ['c', 'e'], ['d', 'e']]
>>> len(P2)
10

On retrouve $\binom52 = 10$. Pour les parties à $3$ éléments, on impose $i < j < k$ :

P3 = [[E[i], E[j], E[k]] for i in range(n) for j in range(i+1, n) for k in range(j+1, n)]

len(P3) vaut 10, c'est-à-dire $\binom53$.

7.3 Les permutations d'un ensemble fini

On construit les débuts de permutations étape par étape, comme dans un arbre : à chaque étape, on prolonge chaque liste déjà obtenue par chacun des éléments qu'elle ne contient pas encore.

def permutations(E):
    P = [[]]
    for etape in range(len(E)):
        P = [p + [x] for p in P for x in E if x not in p]
    return P

>>> permutations([1, 2, 3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> len(permutations([1, 2, 3, 4, 5]))
120

Avec [1, 2, 3], la liste P vaut [[1], [2], [3]] après la première étape ($3$ choix), puis contient $6$ listes de deux éléments ($3 \times 2$), puis les $6$ permutations ($3 \times 2 \times 1 = 3!$). En faisant seulement $k$ étapes, on obtiendrait les $k$-uplets d'éléments distincts.

7.4 Tirer une permutation au hasard

On tire au hasard un élément parmi ceux qui restent, on le retire de la liste, et on l'ajoute à la permutation, jusqu'à ce qu'il ne reste rien.

from random import randint

def permutation_hasard(E):
    reste = list(E)
    P = []
    while len(reste) > 0:
        i = randint(0, len(reste) - 1)
        P.append(reste.pop(i))
    return P

randint(0, len(reste) - 1) tire un indice au hasard dans la liste reste, et reste.pop(i) retire l'élément d'indice i en le renvoyant. Un appel permutation_hasard([1, 2, 3, 4, 5]) peut renvoyer par exemple [4, 1, 5, 3, 2]. On fait $n$ tirages, puis $n - 1$, et ainsi de suite : chacune des $n!$ permutations peut sortir, avec la même chance.