Programmation BUT

Travaux pratiques de Mathématiques

(pour signaler une erreur monnerat@u-pec.fr)

Groupe des permutations.

Quelques rappels

Pour \(n\geq 1\), on note \( \mathfrak{S}_{n}\) le groupe des permutations de \(\{1,\ldots,n\}\). Un élément \(p \in \mathfrak{S}_{n}\) sera représenté par un tableau \(P = [ p(1),p(2),\ldots ,p(n) ]\).

Ainsi, le tableau \(P=[3,4,1,2,6,5]\) représente la permutation \(p\in \mathfrak{S}_{6}\) $$p=\left(\begin{matrix} 1 & 2 & 3 & 4&5&6 \\ 3 & 4 & 1 & 2 & 6 & 5 \end{matrix}\right)$$ i.e $$p(1)=3, p(2)=4, p(3)=1, p(4)=2, p(5)=6, p(6)=5$$

Fonctions de bases en C

On représente une permutation par la structure en C suivante :

#ifndef _PERMUTATION_H
#define _PERMUTATION_H
#define MAX 30
 
typedef struct permutation{
	int n; /* n <= MAX*/
	int  t[MAX];
	int decomp; /* booléen pour 
	   savoir si la permuation 
	   est décomposée en cycles ou pas */
	int num; 
	/*rang de la permutation dans
	 * l'ordre léxicographique
	 * */
} permutation;
 
/* fonctions sur les permutations */
 
permutation Ident(int n);
int Eval(permutation p,int x);
int Egal(permuation p,Permutation q);
permutation Comp(permutation p,permutation q);
permutation Exp(permutation p,long int alpha);
permutation Inv(permutation p);
int Ordre(permutation p);
void Print(permutation p);
permutation Scanf(void);
void Decomp(permutation * p);
void Recomp(permutation * p);
permutation Next(permutation p);
permutation ** Table(int n);
#endif

Le champ n représente la taille, et la liste des images est stockée dans le tableau t. Pour ne pas utiliser d'allocation dynamique, on utilise un tableau de taille MAX, qui ne sera pas complétement utilisé suivant la valeur de \(n\leq MAX\).

  1. Complétez la fonction permutation Ident(int n) qui renvoie la permutation identité de taille n.
  2. Complétez la fonction void Print(permutation p) qui affiche la permutation.
  3. Complétez la fonction permutation Scanf() qui renvoie la permutation saisie sur l'entrée standard (sous la forme [2,3, ....., ]).
  4. Complétez la fonction int Eval(permutation p,int x) qui calcule \(p(x)\).
  5. Complétez la fonction permutation Comp(permutation p,permutation q) qui calcule \( p\circ q\).
  6. Complétez la fonction permutation Inv(permutation p) qui calcule \(p^{-1}\).
  7. Complétez la fonction permutation Exp(permutation p, long int k) qui calcule \(p^{k}\) pour \(k\in {\mathbb Z}\). (méthode naïve)
  8. Complétez la fonction int Ordre(permutation p) qui calcule l'ordre de \(p\).

Décomposition en cycles disjoints

On a vu en cours qu'une permutation se décompose (de manière unique) en produit de cycles à support disjoint (donc qui commutent). Par exemple, $$p=[1,2,6,3,7,4,8,10,5,9] = (3,6,4)\circ (5,7,8,10,9)$$ La décomposition d'une permutation se calcule très simplement, et se ramène au calcul de ses orbites. Dans l'exemple précédent,
  • 1 et 2 sont fixes.
  • L'orbite de 3 est \(\{3,6,4\}\)
  • L'orbite de 5 est \(\{5,7,8,10,9\}\).
Pour représenter la décomposition en produit de cycles, on utilisera le tableau et la représentation suivante : $$[-1,-2,3,6,-4,5,7,8,10,-9]$$
  • On marque la fin d'un cycle avec une valeur négative.
  • Les points fixes figures sous forme de cycle de longueur 1.
Une telle représentation n'est pas unique !
  1. Complétez la fonction void Decomp(permutation *p) qui décompose \(p\) en cycles disjoints.
  2. Complétez la fonction void Recomp(permutation *p) qui remet \(p\) sous forme de liste.
  3. Complétez les fonctions de bases pour qu'elle fonctionne quelque soit la forme des permutations en entrée. En sortie, on renverra toujours une permutation sous forme non décomposée.

Exponentiation rapide

Le calcul naïf de \(n^e\) consiste à calculer \(n\times n\times n\times \ldots \times n\), ce qui coûte \(e-1\) produits.

L'exponentiatation rapide utilise la décomposition binaire de l'exposant :

$$e=\sum_{i=0}^{i=l} a_i 2^i\ \ a_i\in\{0,1\}$$ Ainsi, $$n^e = n^{a_0} . (n^2)^{a_1} . (n^{2^2})^{a_2}\ldots (n^{2^l})^{a_l}$$ Changer la fonction Exp en mettant en oeuvre cette méthode.

Génération des permutations

L'ensemble des permutations est totalement ordonné par l'ordre lexicographiqe. Le plus petit élément est l'identité \([1,2,3,\ldots,n]\), et le plus grand \([n,n-1,\ldots,2,1]\).

Par exemple, pour \(\mathfrak{S}_{4}\), voici la liste ordonnée de ses éléments :

[  1,  2,  3,  4]
[  1,  2,  4,  3]
[  1,  3,  2,  4]
[  1,  3,  4,  2]
[  1,  4,  2,  3]
[  1,  4,  3,  2]
[  2,  1,  3,  4]
[  2,  1,  4,  3]
[  2,  3,  1,  4]
[  2,  3,  4,  1]
[  2,  4,  1,  3]
[  2,  4,  3,  1]
[  3,  1,  2,  4]
[  3,  1,  4,  2]
[  3,  2,  1,  4]
[  3,  2,  4,  1]
[  3,  4,  1,  2]
[  3,  4,  2,  1]
[  4,  1,  2,  3]
[  4,  1,  3,  2]
[  4,  2,  1,  3]
[  4,  2,  3,  1]
[  4,  3,  1,  2]

Complétez la fonction Next qui renvoie la permutation suivante au sens de l'odre lexicographique.

Table du groupe \(\mathfrak{S}_{n}\)

Complétez la fonction permutation ** Table(int n) qui calcule la table du groupe. Les permutations sont ordonnées dans l'ordre croissant.
On rappelle que la table est de dimension \(n!\times n!\).

Pour \(n=3\), la table est $$ \begin{array}{r|*{6}{r}} {\circ}&1&2&3&4&5&6\\\hline {}1&1&2&3&4&5&6\\ {}2&2&1&5&6&3&4\\ {}3&3&4&1&2&6&5\\ {}4&4&3&6&5&1&2\\ {}5&5&6&2&1&4&3\\ {}6&6&5&4&3&2&1\\ \end{array} $$

Travaux à rendre

L'archive téléchargée et complétée avec votre implantation de permutation.c. Vous pouvez tester avec les 4 programmes main1, main2,main3 et main4.

Le travail est à réaliser en binôme, et à rendre ici avant le lundi 30 janvier au soir.

[denis@portable_denis lois]$ ./main1 < permutation1.txt 
Permutation : [13,20,6,9,11,12,3,14,15,5,18,4,16,10,17,1,7,2,8,19]
Ordre : 72
Inverse : [16,18,7,12,10,3,17,19,4,14,5,6,1,8,9,13,15,11,20,2]
Décomposition : [1,13,-16,2,20,19,8,14,10,5,11,-18,3,6,12,4,9,15,17,-7]

 ./main2 < permutation2.txt 
p : [20,6,4,1,2,9,7,14,16,18,13,17,8,11,15,3,19,12,5,10]
q : [6,9,1,13,3,14,17,15,7,4,18,10,19,5,2,16,8,12,20,11]
p*q : [9,16,20,8,4,11,19,15,7,1,12,18,5,2,6,3,14,17,10,13]
q*p : [11,14,13,6,9,7,17,5,16,12,19,8,15,18,2,1,20,10,3,4]
(p*q)^987654321123456789 : [10,6,12,2,14,20,9,16,1,19,13,5,17,15,3,11,8,4,7,18]

[denis@portable_denis lois]$ ./main3
[1,2,3,4]
[1,2,4,3]
[1,3,2,4]
[1,3,4,2]
[1,4,2,3]
[1,4,3,2]
[2,1,3,4]
[2,1,4,3]
[2,3,1,4]
[2,3,4,1]
[2,4,1,3]
[2,4,3,1]
[3,1,2,4]
[3,1,4,2]
[3,2,1,4]
[3,2,4,1]
[3,4,1,2]
[3,4,2,1]
[4,1,2,3]
[4,1,3,2]
[4,2,1,3]
[4,2,3,1]
[4,3,1,2]
[4,3,2,1]

[denis@portable_denis lois]$ ./main4
     |   1 |   2 |   3 |   4 |   5 |   6 | 
------------------------------------------
  1  |   1 |   2 |   3 |   4 |   5 |   6 | 
  2  |   2 |   1 |   5 |   6 |   3 |   4 | 
  3  |   3 |   4 |   1 |   2 |   6 |   5 | 
  4  |   4 |   3 |   6 |   5 |   1 |   2 | 
  5  |   5 |   6 |   2 |   1 |   4 |   3 | 
  6  |   6 |   5 |   4 |   3 |   2 |   1 |