Mathématiques du traitement du signal/Fonctions de permutation
Fonctions de permutation en informatique
modifierUn 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 la fonction (c'est un polynôme de degré N-2) :
vaut zéro pour tous ces nombres
Pour construire une fonction qui envoie aN sur a1 et tous les autres nombres sur zéro, il faut prendre la fonction :
je vais noter cette fonction pour nous rappeler qu'elle vaut zéro partout sauf pour .
de même, la fonction qui envoie a1 sur a2 et tous les autres nombres sur zéro est :
où j'ai noté ; maintenant, tu peux remarquer que :
vaut zéro partout sauf en et en (où elle vaut et ), voila que ça commence à prendre forme. La formule finale est :
qui vaut en 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) :
et donc
ce qui permet d'écrire :
que tu peux simpifier en
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 :
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.