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).
Elle dérivera du type tuple afin d'être immutable et donc de pouvoir être utilisée comme clef dans un dictionnaire.
Ceci implique de définir la méthode __new__ au lieu de __init__ (voir ici, cellule 23.)
On pourra l'initialiser avec un tuple, une liste ou une chaîne d'entiers de $1$ à $n$.
>>> 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)
La composition des permutations s'effectuera en surchargeant la méthode spéciale __mul__ (opérateur *).
On pourra implanetr l'action à droite sur le mots en surchargeant __rmul__.
Implanter les méthodes inverse, code, des_num (nombre de descentes), descents (liste des descentes),
inv_num (nombre d'inversions), maj (indice majeur, c'est la somme des descentes),
imaj (indice majeur de l'inverse), reduced_dec (décomposition réduite), cycles (decomposition en cycles).
La reconstitution d'une permutation à partir de son code sera une méthode de classe from_code, et de même
pour la reconstitution à partir des cycles (from_cycles). La méthode spéciale __call__ permettra
de renvoyer la valeur de $p(i)$ avec la syntaxe p(i) (qui vaut p[i-1]).
Écrivez aussi une fonction (ou mieux, un générateur) renvoyant les permutations (sous forme de tuples simples) d'une liste/tuple/chaîne donnée. On pourra utiliser la syntaxe suivante pour le générateur.
La fonction Permutations prendra comme paramètre un entier $n$ et renverra un générateur sur les permutations (type Permutation) de $1,\ldots,n$.
La standardisation d'un mot $w$ sur un alphabet ordonné est l'unique permutation $\sigma={\rm std\,}(w)$ ayant les mêmes inversions que $w$. Son inverse effectue le tri de $w$ par échanges adjacents. On peut aussi la calculer et numérotant de gauche à droite les occurences de la plus petite lettre, puis celles de la suivante, etc. Par exemple (avec $A=10,B=11,C=12)$ $$w = fcahhddabahc$$ $$\sigma= 951AB78243C6$$
On rajoutera des fonctionnalités dans les TP suivants. Notez qu'il est utile de disposer de fonctions indépendantes
qui font les mêmes calculs que les méthodes de la classe Permutation.
Vous documenterez votre code en incluant au moins un exemple pour chaque fonction ou méthode. L'aide en ligne ainsi générée pourra ressembler à ceci :
>>> import permutations
>>> help(permutations)
Help on module permutations:
NAME
permutations - # permutations.py
CLASSES
builtins.tuple(builtins.object)
Permutation
class Permutation(builtins.tuple)
| 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)
| >>>
|
| Method resolution order:
| Permutation
| builtins.tuple
| builtins.object
|
| Methods defined here:
|
| __call__(self, i)
| Apply permutation to i.
|
| >>> w = Permutation([5,2,4,1,3])
| >>> w(3)
| 4
|
| __mul__(self, y)
| Return self*value.n
|
| code(self)
| Lehmer code.
|
| >>> w.code()
| [4, 1, 2, 0, 0]
|
| cycles(self)
| Cycles of permutation.
|
| >>> w = Permutation([5,2,4,1,3])
| >>> w.cycles()
| [[1, 5, 3, 4], [2]]
|
| des_num(self)
| Number of descents of permutation.
|
| >>> w = Permutation([5,2,4,1,3])
| >>> w.des_num()
| 2
|
| descents(self)
| Descents of permutation (as sublist of [1,...,n-1])
|
| >>> w = Permutation([5,2,4,1,3])
| >>> w.descents()
| [1, 3]
|
| imaj(self)
| Major index of inverse permutation.
|
| >>> w = Permutation([5,2,4,1,3])
| >>> w.imaj()
| 8
|
| inv_num(self)
| Number of inversions.
|
| >>> w = Permutation([5,2,4,1,3])
| >>> w.inv_num()
| 7
|
| inverse(self)
| Inverse permutation
|
| >>> w = Permutation([5,2,4,1,3])
| >>> w.inverse()
| (4, 2, 5, 3, 1)
| >>> _ * w
| (1, 2, 3, 4, 5)
|
| maj(self)
| Major index (sum of descents) of permutation.
|
| >>> w = Permutation([5,2,4,1,3])
| >>> w.maj()
| 4
|
| reduced_dec(self)
| A reduced decomposition of permutation.
|
| >>> w.reduced_dec()
| [3, 4, 1, 2, 3, 2, 1]
|
| ----------------------------------------------------------------------
| Class methods defined here:
|
| from_code(cc) from builtins.type
| Permutation of Lehmer code c.
|
| >>> c = [4, 1, 2, 0, 0]
| >>> Permutation.from_code(c)
| (5, 2, 4, 1, 3)
|
| from_cycles(cc) from builtins.type
| Permutation from a list of cycles, including fixed points
|
| >>> Permutation.from_cycles([[1, 5, 3, 4], [2]])
| (5, 2, 4, 1, 3)
|
| from_reduced_dec(rd, n) from builtins.type
| Permutation from a reduced decomposition.
|
| >>> Permutation.from_reduced_dec([3, 4, 1, 2, 3, 2, 1],5)
| (5, 2, 4, 1, 3)
|
| ----------------------------------------------------------------------
| Static methods defined here:
|
| __new__(cls, x)
| Create and return a new object. See help(type) for accurate signature.
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
| ----------------------------------------------------------------------
| Methods inherited from builtins.tuple:
|
| __add__(self, value, /)
| Return self+value.
|
| __contains__(self, key, /)
| Return key in self.
|
| __eq__(self, value, /)
| Return self==value.
|
| __ge__(self, value, /)
| Return self>=value.
|
| __getattribute__(self, name, /)
| Return getattr(self, name).
|
| __getitem__(self, key, /)
| Return self[key].
|
| __getnewargs__(...)
|
| __gt__(self, value, /)
| Return self>value.
|
| __hash__(self, /)
| Return hash(self).
|
| __iter__(self, /)
| Implement iter(self).
|
| __le__(self, value, /)
| Return self<=value.
|
| __len__(self, /)
| Return len(self).
|
| __lt__(self, value, /)
| Return self<value.
|
| __ne__(self, value, /)
| Return self!=value.
|
| __repr__(self, /)
| Return repr(self).
|
| __rmul__(self, value, /)
| Return self*value.
|
| count(...)
| T.count(value) -> integer -- return number of occurrences of value
|
| index(...)
| T.index(value, [start, [stop]]) -> integer -- return first index of value.
| Raises ValueError if the value is not present.
FUNCTIONS
Permutations(n)
Generator for permutations of 1..n as type Permutation
>>> S3 = Permutations(3)
>>> next(S3)
(1, 2, 3)
>>> type(_)
<class 'permutations.Permutation'>
genperms(ll)
Generator for permutations of list or tuple
>>>it = genperms([1,3,5])
>>> [next(it) for i in range(6)]
[[1, 3, 5], [1, 5, 3], [3, 1, 5], [3, 5, 1], [5, 1, 3], [5, 3, 1]]
gnome_sort(ll)
Returns (sorted(ll), reduced decomposition)
>>> gnome_sort([5,4,3,2,1])
([1, 2, 3, 4, 5], [1, 2, 3, 4, 1, 2, 3, 1, 2, 1])
listperms(ll)
Same as genperms, but returns a list of lists
permlist(n)
Same as Permutations, but returns a list of lists
reduce(...)
reduce(function, sequence[, initial]) -> value
Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5). If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty.
standardization(w)
Returns the standardization of a list, tuple, or word
>>> standardization('gagbga')
(4, 1, 5, 3, 6, 2)
>>> standardization([8,4,8,2,8,1])
(4, 3, 5, 2, 6, 1)
FILE
/home/jyt/python/combi/permutations.py
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.
Voir aussi ici.
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$.