+----------------------------------------------+
|                                              |
|          Etude du groupe symétrique          |
|                                              |
+----------------------------------------------+

Par Stéphane Dumas
Date de dernière modification : 15/05/08

+-------------+
| Description |
+-------------+

Ce groupe de fonctions contient tout ce qu'il faut pour étudier les permutations d'un ensemble fini.

Pour réussir cela, j'ai été amené à stocker les permutations de l'ensemble {1,2,3,...,n} sous la forme de listes contenant dans l'ordre les images des valeurs 1,2,3,...n par ladite permutation.
Désormais, lorsque vous verrez le mot permutation, il faudra comprendre qu'il s'agit de la liste de ses images.

Comme on manipule également des cycles, ceux-ci sont stockés un peu différemment : un cycle est stocké sous la forme usuelle {a,b,c,d,...} convertie en chaîne de caractères.
Le plus simple pour comprendre est d'utiliser une fois la fonction 'perm2cyc'...


+----------------------+
| Utilisation, syntaxe |
+----------------------+

Dans ce tutorial, "n" et "k" désignent des entiers naturels, "perm","perm1","perm2" des permutations, "list" une liste quelconque, "mat" une matrice de permutation et "cycs" une liste de cycles.

Le pack se compose des fonctions suivantes :

id(n) 			-> renvoie la permutation identité de l'ensemble [[1,n]]
randperm(n)		-> renvoie une permutation au hasard de l'ensemble [[1,n]]
randperm(list)		-> renvoie une permutation au hasard des éléments de la liste "list"

mat2perm(perm)		-> renvoie la matrice de permutation associée à la permutation "perm".
perm2mat(mat)		-> transforme une matrice de permutation en la permutation correspondante (sous forme de liste)

compose(perm1,perm2)	-> renvoie la permutation composée   "perm1" o "perm2"
puisperm(perm,n)	-> renvoie la n-ème itérée de la permutation "perm", c'est-à-dire "perm" composée n fois avec elle-même.

fix(perm)		-> renvoie la liste des points fixes de la permutation "perm"
orbite(k,perm)		-> renvoie l'orbite de l'élément "k" suivant la permutation "perm"

perm2cyc(perm)		-> décompose la permutation en produit de cycles à supports disjoints et renvoie la liste de ces cycles.
cyc2perm(cycs)		-> effectue l'opération inverse (en fait, ici, les cycles n'ont pas besoin d'être à support disjoints). La fonction renvoie une permutation de [[1,n]] où n est la plus grande valeur rencontrée dans les cycles.

ordre(perm)		-> renvoie l'ordre d'une permutation (c'est-à-dire le plus petit entier "k" tel que la k-ème itérée de "perm" soit l'identité).

nbinv(perm)		-> renvoie le nombre d'inversions de la permutation "perm"

signat(perm)		->
signat1(perm)		-> renvoient toutes les 3 la signature de "perm" en utilisant 3 méthodes différentes (la première étant la plus rapide).
signat2(perm)		->


+---------------+
| Avertissement |
+---------------+

Pour éviter de ralentir considérablement les opérations, aucune vérification des données n'est faite par les fonctions.
Si le paramètre que vous leur donner en entrée n'est pas correct les fonctions risquent au mieux de retourner une erreur, au pire de renvoyer n'importe quoi sans vous prévenir de l'erreur commise.