Mathématiques du traitement du signal/Fonctions de permutation

Fonctions de permutation en informatique

Un petit camarade informaticien me demandait récemment par mail comment comment construire une fonction de permutation (qu'il a appelé valeur complémentaire):

J'ai besoin de tes lumières pour une quest° simple mais q je crois pas pouvoir trouver seul. 
En fait je pense que c'est une équation que j'arrive pas à solutionner .
tu es prêt ?
alors j'ai trois valeurs { 0, 1, 2}
jusque là je pense être clair !
Maintenant il faut que si je prends une valeur de l'ensemble je retombe automatiquement sur les deux autres,
je crois que ça pt s'appeler une valeur complémentaire.

Exemple j'ai 2 valeurs {0, 1}
l'équation complémentaire est 1-X
car 0 donne 1 
et 1 donne 0

Mais avec {0 1 2} je trouve pas
je dirai
2-x
1-x
car le 1 fait bloquer le processus .....
Et je dois trouver un substitut pour un élémen t de détail sur 1 de mes sites . salut

C'est une question suffisamment générique en informatique pour que cela vaille le coup d'y consacrer un peu de place ici.

pour un ensemble de N nombres (ici 3), il te faut N-1 (ici 2) fonctions. Elles doivent toutes être construites sur le même modèle, qui vient du fait que si tu as N-1 nombres $a_1, a_2, \dots, a_{N-1}$ la fonction (c'est un polynôme de degré N-2) :

$F(x) = (x-a_1) (x-a_2) \cdots (x-a_{N-1})$ vaut zéro pour tous ces nombres

Pour construire une fonction qui envoie aN sur a1 et tous les autres nombres $(a1,\dots,a_{N-1})$ sur zéro, il faut prendre la fonction :

$G(x) = {F(x)\over F(a_N)}\, a_1$

je vais noter cette fonction $G[a_N](x)$ pour nous rappeler qu'elle vaut zéro partout sauf pour $a_N$.

de même, la fonction qui envoie a1 sur a2 et tous les autres nombres $(a_3,\dots, a_N)$ sur zéro est :

$G[a_1](x) = F[a_3,\dots,a_N](x) / F[a_3,\dots,a_N](a_1) a_2$

où j'ai noté $F[a_3,\dots,a_N](x) = (x-a_3) (x-a_4) \ldots (x-a_N)$ ; maintenant, tu peux remarquer que :

$H(x) = G[a_1](x) + G[a_N](x)$

vaut zéro partout sauf en $a_1$ et en $a_N$ (où elle vaut $a_2$ et $a_1$), voila que ça commence à prendre forme. La formule finale est :

$K(x) = G[a_1](x) + G[a_2](x) + \ldots + G[a_N](x) = \sum_{n=1}^N G[a_n](x)$

qui vaut $a_{n+1}$ en $a_n$ pour tous les n (elle décale tout le monde d'un indice).

si on applique cela à ton problème (mais comme ça tu pourras résoudre n'importe quel problème du genre) :

$\{a_1, a_2, a_3\} = \{0, 1, 2\}$

$\left\{ \begin{matrix} F[1,2](x) &=& (x-1) (x-2) \\ F[0,2](x) &=& x \,(x-2) \\ F[0,1](x) &=& x \,(x-1) \end{matrix}\right.$

et donc

$\left\{ \begin{matrix} G[0](x) &=& \displaystyle {F[1,2](x) \over F[1,2](0) }\, 1 &=& {(x-1)\,(x-2) \over 2}\\ G[1](x) &=& \displaystyle {F[0,2](x) \over F[0,2](1)}\, 2 &=& - x \, (x-2) \, 2\\ G[2](x) &=& \displaystyle {F[0,1](x) \over F[0,1](2)}\, 0 &=& 0 \end{matrix}\right.$

ce qui permet d'écrire :

$K(x) = {(x-1)\,(x-2) \over 2} - x \, (x-2) \, 2 + 0$

que tu peux simpifier en $K(x) = (x-2) \, ( {x-1\over 2} - 2 x)$

Cette fonction a bien la propriété d'envoyer 0 sur 1, 1 sur 2 et 2 sur 0.

tu peux obtenir de la même façon une seconde fonction qui envoie 0 sur 2, 1 sur 0 et 2 sur 1, il s'agit de :

$L(x) = {F[1,2](x) \over F[1,2](0)}\, 2 + {F[0,2](x) \over F[0,2](1) }\, 0 + {F[0,1](x) \over F[0,1](2)}\, 1$

et voilà, j'espère que cela répond à ta question et surtout que cela va te permettre de calculer toi même toutes les fonctions de ce genre dont tu auras besoin.