\documentclass[twocolumn,a4paper]{article}
\usepackage{french,tp}
\advance\topmargin -1cm
\advance\textheight 1cm

\begin{document}

\begin{header}
\Huge Huitième TP
\bigskip
\end{header}

\subsection*{Permutation}
On appelle {\em  permutation} toute fonction
bijective de $\{1...n\}$ dans $\{1...n\}$.
La valeur d'une permutation est stockée
dans un tableau à $n$ cases.
La case numéro $i$ contient la valeur
de l'image de $i$ par la permutation.

On définit donc un type
{\tt Perm} qui vaut
{\tt ARRAY[1..n] OF INTEGER}.
Pour l'exemple, on choisira
la valeur 4 pour la constante {\tt n}.

On note alors $[f(1), f(2), f(3), f(4)]$
la permutation qui à $i$ associe $f(i)$.
Par exemple, $[1,2,3,4]$ est l'identité.

\subsubsection*{Premières procédures}
$\bullet$
Faire une procédure {\tt Entrée}
dont l'argument est une variable de type {\tt Perm}
et qui fait la saisie au clavier d'une permutation.
Elle demande successivement l'image des
nombres 1, 2, ... $n$.

$\bullet$
Faire une procédure {\tt Affiche}
dont l'argument est une variable de type {\tt Perm}
et qui affiche la valeur d'une permutation.

\subsubsection*{Vérification}
Un tableau de type {\tt Perm} peut stocker
toute fonction de $\{1...n\}$ dans $\{1...n\}$.
Mais toutes ne sont pas des permutations.
Par exemple, $[1,4,2,4]$ n'est pas bijective.

$\bullet$
Faire une fonction {\tt Bijection} dont
le résultat est de type {\tt BOOLEAN}
et qui vérifie que le contenu d'une
variable de type {\tt Perm} est bien
une bijection.

$\bullet$
Modifier {\tt Entrée} de telle sorte
que l'ordinateur refuse les entrées non valides.

\subsection*{Groupe des permutations}
\subsubsection*{La loi de groupe}
La composition des applications de $\{1...n\}$
définit une loi de groupe sur les permutations.

$\bullet$ $\bullet$
Faire une procédure {\tt Compose} qui calcule
la composition de deux permutations.
Cette procédure a donc trois arguments :
deux pour les opérandes $f$ et $g$ et
un troisième pour le résultat $g \circ f$.
Par exemple, la composition de $f = [2,3,1,4]$
et $g = [3,4,2,1]$
est $g \circ f = [4,2,3,1]$.
\[\begin{array}{ccccc}
  &    f    &   &    g    &   \cr
1 & \mapsto & 2 & \mapsto & 4 \cr
2 & \mapsto & 3 & \mapsto & 2 \cr
3 & \mapsto & 1 & \mapsto & 3 \cr
4 & \mapsto & 4 & \mapsto & 1 \cr
\end{array}\]

$\bullet$ $\bullet$
Faire une procédure {\tt Inverse} qui calcule
l'inverse d'une permutation.
Par exemple, l'inverse de $f = [2,3,1,4]$
est $f^{-1} = [3,1,2,4]$.
\[\begin{array}{ccccc}
  &    f    &   & f^{-1}  &   \cr
1 & \mapsto & 2 & \mapsto & 1 \cr
2 & \mapsto & 3 & \mapsto & 2 \cr
3 & \mapsto & 1 & \mapsto & 3 \cr
4 & \mapsto & 4 & \mapsto & 4 \cr
\end{array}\]

\subsubsection*{Ordre d'une permutation}
Soit $f$ un élément d'un groupe,
on note $f^k = f \circ ... \circ f$
la composition de $f$ par lui-même
$k$ fois.

Le plus petit $k$ tel que $f^k$
soit égal à l'identité est appelé
{\em ordre de $f$}.

$\bullet$
Faire une fonction {\tt Identité}
dont le résultat est un {\tt BOOLEAN}
qui dit si la permutation donnée
en argument est l'identité.

$\bullet$ $\bullet$
Faire une fonction {\tt Ordre} qui calcule
l'ordre d'une permutation.
Par exemple, l'ordre de $f = [2,3,1,4]$
est 3.

\subsection*{Les cycles}
On définit ici une autre représentation des permutations :
au lieu de montrer quel est l'image de chaque nombre,
on représente un permutation en indiquant les cycles.
Par exemple, la décomposition en cycle de $[2,3,1,4]$
sera notée $(1,2,3)(4)$.
En sens inverse,
la notation $(1,2)(3,4)$ correspond donc à $[2,1,4,3]$.

\begin{center}
\divide\unitlength 2
\begin{picture}(344,119)
\special{psfile=permut.eps vscale=50 hscale=50}
\end{picture}
\end{center}

$\bullet$ $\bullet$ $\bullet$
Faire une fonction {\tt Cycles} qui affiche
la décomposition en cycles d'une permutation.

\subsection*{Énumération des permutations \small (difficile)}
$\bullet$ $\bullet$ $\bullet$ $\bullet$
On peut réfléchir à un programme
qui affiche successivement, et une seule
fois chacune, toutes les permutations.
Il faut éviter de calculer les $n^n$
applications de $\{1...n\}$ dans $\{1...n\}$.

\end{document}
