Fonction de permutation paramétrée
Je cherche un moyen de construire une fonction qui fonctionnerait de la manière décrite dans l'image suivante:
Autrement dit, je veux qu'il permute les éléments dans un tableau donné pour les mettre dans un ordre différent en fonction d'un paramètre que je lui donne, de sorte que les nombres de mon choix dans l'ensemble d'origine (ceux que j'ai marqués avec un fond gris) seraient tous se terminent comme une plage continue au début du tableau de sortie (à gauche de la ligne épaisse), tandis que tous les autres éléments (fond rouge) se retrouveraient aux positions restantes dans ce tableau (à droite de la ligne épaisse) .
L'ordre de ces éléments dans chacune des plages de sortie (gris ou rouge) n'a pas d'importance pour moi. Ils peuvent être mis dans n'importe quel ordre arbitraire par cette fonction, ce qui est plus simple à calculer pour un choix particulier d'éléments d'entrée sélectionnés (gris). La seule chose qui compte, c'est que tous ces éléments sélectionnés (gris) se retrouvent d'un côté de la frontière, tandis que les autres éléments (rouge) se retrouvent de l'autre côté de cette limite, et les deux plages sont continues.
Cette fonction doit être paramétrable pour que, parmi toutes les permutations possibles de ce tableau, je puisse choisir cette permutation particulière qui place les éléments dans cet ordre particulier en spécifiant simplement un paramètre numérique (ou des paramètres) dans la formule de la fonction.
Un paramètre numérique est préférable, car il n'y a qu'une seule permutation qui place tous les éléments dans cet ordre particulier, et ce nombre pourrait être le "numéro d'identification" de cette permutation, mais si cela était difficile à atteindre, plusieurs paramètres numériques sont acceptables , tant qu'il ne dépasse pas le nombre d'éléments choisis (ce qui ne vaut probablement pas la peine de toute façon).
Existe-t-il un moyen de construire une formule pour une telle fonction de manière systématique, étant donné un sous-ensemble d '"éléments choisis" du tableau d'entrée? Peut-être quelque chose basé sur l'arithmétique modulaire ou les champs finis? Une recherche rapide sur le Web m'a donné un terme appelé "polynômes de permutation" qui, à première vue, semble être lié à ce problème, mais toutes les ressources que j'ai pu trouver à leur sujet sont des mathématiques épaisses qui semblent exiger beaucoup de connaissances dans ce domaine pour même comprendre ce qui se passe (je suis juste un ingénieur / programmeur informatique à la recherche d'une solution à un problème de programmation, pas un mathématicien professionnel: q)
Bien entendu, n'importe quelle fonction peut être placée dans une table de consultation. Mais ce n'est pas ce que je recherche, car cela nécessiterait une table de recherche de la même taille que l'ensemble des entrées, ce qui serait excessif.
Edit:
Une chose qui me vient à l'esprit est l'exponentiation modulaire, car dans les modules premiers, lorsqu'une racine primitive est choisie comme base, et l'exposant est notre$x$, alors chaque puissance de cette base est unique (période maximale) et la séquence résultante est une permutation de la séquence originale (cependant, elle commence et se termine toujours par 1, et il y a toujours $N-1$au milieu). Mais de cette façon, je ne peux obtenir que quelques permutations, pas toutes les permutations possibles .
Élever cette fonction exponentielle à une autre puissance$p$ sélectionne uniquement tous les $p$e élément de cette séquence, donc de cette façon je ne peux obtenir une séquence que pour une autre racine primitive (à condition que $p$correspond à la taille du module moins un, car sinon la période se divise en cycles plus courts, comme pour une autre base qui n'est pas une racine primitive). Peut-être y a-t-il un autre moyen de mélanger ces chiffres que l'exponentiation?
Réponses
Comme vous le savez peut-être, un inversible (non singulier) $n\times n$ matrice contenant des entrées $F_q$, où q =$p^k$ et $p$ prime définit un espace image fini, c'est donc une permutation de $F_q^n$. C'est, étant donné$M \in GL_n(q)$ où $q=p^k$ et $k\geq 1$, comme $M$ n'est pas singulier, il définit une permutation sur les tuples dans $F_q^n$. C'est une conséquence de$M$ étant un élément du groupe linéaire général (matrices inversibles) et la multiplication matricielle étant réduite modulo $p$ ou $f(x)$ si $F_q$ c'est un champ d'extension de diplôme $n$.
Vous avez mentionné les polynômes de permutation sur les champs finis contenant $q$éléments. Il en résulte que le groupe de linéarisé Permutation sur Polynomials$F_{q^n}$ sous composition et le groupe de matrices inversibles sur $F_q$sous multiplication sont isomorphes. Un polynôme linéarisé sur$F_{q^n}$ peut être défini comme $p(X) = \sum_{i=0}^{n-1} \alpha_i x^{q^i} \; \alpha_i \in F_{q^n}$ et nous avons quelques moyens mathématiques pour prouver s'il s'agit d'un polynôme de permutation ou non.
Tout d'abord, expliquez la relation entre les polynômes de degré $n-1$ plus de $F_q$ et vecteurs-tuples sur $F_q$ de dimension $n$. La carte$\varphi$ envoie un vecteur à un polynôme et vice-versa:
$$\varphi : F_q^n \mapsto F_{q^n}$$ $$\varphi(a_0,\ldots,a_{n-1}) \mapsto \sum_{i=0}^{n-1}a_ix^i$$
Maintenant, pour établir une relation entre les matrices inversibles sur $F_q$ et polynômes de permutation linéaires sur $F_{q^n}$, il faut définir la carte $\phi$ qui envoie un polynôme linéarisé $p(X)$ à une matrice inversible $M_{p(X)}$.
$$\phi: \mathcal{L}_n \simeq GL_n(q)$$ $$\phi(p(X)) \mapsto \{\varphi^{-1}(p(\varphi(e_1)),\ldots, \varphi^{-1}(p(\varphi(e_n)))\}$$
Clairement, les deux cartes sont linéaires et s'accordent sur la même image en appliquant $\varphi$ à l'entrée de $p(X)$ et $\varphi^{-1}$ à sa sortie.
$$M_{p(X)}\cdot \sum_{i=1}^n \alpha_i e_i = \varphi^{-1}(p(\sum_{i=1}^n \varphi(\alpha_i e_i)))$$ $$\sum_{i=1}^n M_{p(X)} \cdot \alpha_i e_i = \varphi^{-1}(\sum_{i=1}^n p(\varphi(\alpha_i e_i)))$$
En termes d'informatique, vous n'avez pas besoin de calculer des polynômes à permutation linéarisés, mais vous pouvez travailler avec des matrices carrées inversibles sur un champ premier ou un champ d'extension d'un tel champ. Pourquoi? Eh bien, il a été prouvé que les polynômes à permutation linéaire sur$F_{q^n}$ et matrices inversibles sur $F_q$définir une action équivalente par la relation exposée ci-dessus. Ces matrices sont des éléments du groupe linéaire général$GL_n(q)$. Cette définition garantit que, étant donné une matrice inversible$M$ plus de $F_q$, l'opération $M \cdot x = b$ permutes $x$. Par conséquent, ici la multiplication définit une bijection sur l'ensemble des éléments de$F_q$.
Il y a plus de travail dans la branche de la combinatoire. Par exemple, le groupe symétrique sur$n$ symboles $S_n$ comprend toutes les permutations de degré $n$. De là, vous pouvez calculer le$k$ème permutation d'un ensemble $S$ ayant $n$ éléments par la décomposition dans le système numérique factoriel, qui vous donne une liste de quotient qui définit que $k$e permutation. Un autre point, est celui que vous avez mentionné, qui est basé sur l'exponentiation modulaire. Pour cela, comprenez qu'avoir une grosse commande$r$ st $g^r \equiv_p 1$ est convaincu que ce n'est pas pratique pour les permutations, car vous devez calculer chaque image $g^i$ jusqu'à $g^r$, qui est limité par la longueur de votre ensemble $S$ qui va être permuté.