M1 Combinatoire - TP1 : Python et sympy

Une classe combinatoire : les permutations

L'objectif est d'écrire un module permutations.

Implantez en pur Python une classe Permutation et munissez la des méthodes correspondant aux algorithmes vus en cours (selon ce qui aura déjà été vu).

Écrivez aussi une fonction (ou mieux, un générateur) renvoyant les permutations d'une liste donnée. Un début de module permutations pourrait ressembler à ceci.

>>> import permutations
>>> help(permutations)
Help on module permutations:

NAME
    permutations

FILE
    /home/jyt/monge/W3/M1_combi/permutations.py

CLASSES
    __builtin__.object
        Permutation

    class Permutation(__builtin__.object)
     |  Permutations of 1..n, represented as tuples of integers.
     |
     |  The initialization x can be a tuple, or list of integers or strings of digits,
     |  or a single string of single digits.
     |  >>> Permutation('53412')
     |  (5, 3, 4, 1, 2)
     |  >>> Permutation([5,3,4,1,2])
     |  (5, 3, 4, 1, 2)
     |  >>> Permutation(('5','3','4','1','2'))
     |  (5, 3, 4, 1, 2)
     |  >>>
     |
     |  Methods defined here:
     |
     |  __call__(self, i)
     |
     |  __eq__(self, other)
     |
     |  __hash__(self)
     |
     |  __init__(self, x)
     |      w is x as a tuple on integers, and d is x as a dictionary {i:x[i]}.
     |
     |  __mul__(self, y)
     |      composition of permutations: x*y computes  x o y.
     |
     |  __ne__(self, other)
     |
     |  __repr__(self)
     |
     |  code(self)
     |
     |  cycles(self)
     |
     |  des_num(self)
     |
     |  descents(self)
     |
     |  imaj(self)
     |
     |  inv_num(self)
     |
     |  inverse(self)
     |
     |  maj(self)
     |
     |  reduced_dec(self)
     |
     |  ----------------------------------------------------------------------
     |  Class methods defined here:
     |
     |  from_code(cls, cc) from __builtin__.type
     |
     |  from_cycles(cls, cc) from __builtin__.type
     |
     |  from_reduced_dec(cls, rd, n) from __builtin__.type
     |
     |  ----------------------------------------------------------------------
     |  Data descriptors defined here:
     |
     |  __dict__
     |      dictionary for instance variables (if defined)
     |
     |  __weakref__
     |      list of weak references to the object (if defined)

FUNCTIONS
    bubble_sort(ll)

    listperms(ll)

    permutations(n)

    standardization(w)

Dans un premier temps, on ne cherchera pas un algorithme efficace pour engendrer les permutations. Il y en a un dans le module itertools, mais il sera utile de coder en deux lignes l'algorithme récursif le plus naïf afin de se préparer à d'autres situations.

Il y a des exemples ici.

Calcul symbolique avec sympy

Le système de calcul formel sympy se présente sous forme d'un paquetage python.

Affichez le tutoriel de sympy. Ne lisez pas tout. Repérez rapidement comment définir des variables et former des expressions.

Essayer la commande expand : retrouvez le triangle de Pascal en développant \((1+x)^n\). pour \(n\) de 1 à 14.

Il faut être capable de récupérer les coefficients d'un polynôme ou d'un développement limité. Python est un langage orienté objet. Les résultats de vos calculs sont des objets.

Rappel : On accède aux attributs d'un objet X au moyen de la fonction dir : dir(X) vous dit tout ce que X sait faire. Ayant repéré une fonction f ou une méthode X.f, on accède à son aide en ligne au moyen de help(f).

Trouvez comment former la liste des coefficients d'un polynôme ou d'un développement.

Testez cette méthode sur \((1+x)^n\) et \((1−x)^{−m}\) pour quelques valeurs de \(n\) et \(m\).

In []: