Función de permutación parametrizada
Estoy buscando una forma de construir una función que funcione de la forma que se muestra en la siguiente imagen:
Es decir, quiero que permute los elementos en una matriz dada para ponerlos en un orden diferente dependiendo de un parámetro que le dé, de modo que los números de mi elección del conjunto original (los que marqué con fondo gris) sean todos terminan como un rango continuo al comienzo de la matriz de salida (a la izquierda de la línea gruesa), mientras que todos los demás elementos (fondo rojo) terminarían en las posiciones restantes en esa matriz (a la derecha de la línea gruesa) .
El orden de esos elementos en cada uno de los rangos de salida (gris o rojo) no me importa. Se pueden poner en cualquier orden arbitrario por esa función, lo que sea más simple de calcular para una elección particular de elementos de entrada seleccionados (gris). Lo único que importa es que todos esos elementos seleccionados (grises) terminan en un lado del límite, mientras que otros elementos (rojos) terminan en el otro lado de ese límite, y los dos rangos son continuos.
Esta función debe ser parametrizable para que, de todas las posibles permutaciones de esta matriz, pueda elegir esa permutación particular que ponga los elementos en ese orden en particular simplemente especificando algún parámetro numérico (o parámetros) en la fórmula de la función.
Es preferible un parámetro numérico, ya que solo hay una permutación que coloca todos los elementos en este orden en particular, y este número podría ser el "número de identificación" de esa permutación, pero si eso fuera difícil de lograr, varios parámetros numéricos son aceptables. , siempre que no exceda la cantidad de elementos elegidos (lo que probablemente haría que no valiera la pena el esfuerzo de todos modos).
¿Hay alguna manera de construir una fórmula para dicha función de manera sistemática, dado un subconjunto de "elementos elegidos" de la matriz de entrada? ¿Quizás algo basado en aritmética modular o campos finitos? Una búsqueda rápida en la web me dio un término llamado "polinomios de permutación" que a primera vista parece estar relacionado con este problema de alguna manera, pero todos los recursos que pude encontrar sobre ellos son algunas matemáticas complejas que parecen requerir mucha experiencia en ese campo. incluso para entender lo que está pasando (solo soy un ingeniero / programador de TI que busca una solución para algún problema de programación, no un matemático profesional: q)
Por supuesto, cualquier función se puede poner en una tabla de búsqueda. Pero eso no es lo que estoy buscando, porque eso requeriría una tabla de búsqueda del mismo tamaño que el conjunto de entrada completo, lo que sería una exageración.
Editar:
Una cosa que me viene a la mente es la exponenciación modular, ya que en los módulos primos, cuando se elige una raíz primitiva como base, y el exponente es nuestro$x$, entonces cada potencia de esa base es única (período máximo) y la secuencia resultante es una permutación de la secuencia original (sin embargo, siempre comienza y termina con 1, y siempre hay $N-1$en el medio). Pero de esta manera solo puedo obtener algunas permutaciones, no todas las permutaciones posibles .
Elevando esta función exponencial a alguna otra potencia$p$ solo selecciona cada $p$th elemento de esta secuencia, por lo que de esta manera solo puedo obtener una secuencia para otra raíz primitiva (siempre que $p$es coprime al tamaño del módulo menos uno, porque de lo contrario el período se rompe en ciclos más cortos, como para alguna otra base que no es una raíz primitiva). ¿Quizás haya alguna otra forma de barajar esos números que la exponenciación?
Respuestas
Como sabrá, un invertible (no singular) $n\times n$ matriz que tiene entradas sobre $F_q$, donde q =$p^k$ y $p$ prime define un espacio de imagen finito, por lo que es una permutación de $F_q^n$. Esto es, dado$M \in GL_n(q)$ dónde $q=p^k$ y $k\geq 1$, como $M$ no es singular, define una permutación sobre las tuplas en $F_q^n$. Esta es una consecuencia de$M$ siendo un elemento del grupo lineal general (matrices invertibles) y la multiplicación de matrices se reduce módulo $p$ o $f(x)$ Si $F_q$ es un campo de extensión de grado $n$.
Mencionaste polinomios de permutación sobre campos finitos que contienen $q$elementos. El resultado es que el grupo de linealizado de permutación sobre polinomios$F_{q^n}$ bajo composición y el grupo de matrices invertibles sobre $F_q$bajo multiplicación son isomorfos. Un polinomio linealizado sobre$F_{q^n}$ Puede ser definido como $p(X) = \sum_{i=0}^{n-1} \alpha_i x^{q^i} \; \alpha_i \in F_{q^n}$ y tenemos algunas formas matemáticas de demostrar si es un polinomio de permutación o no.
Primero, explique la relación entre polinomios de grado $n-1$ encima $F_q$ y vectores-tuplas sobre $F_q$ de dimensión $n$. El mapa$\varphi$ envía un vector a un polinomio y viceversa:
$$\varphi : F_q^n \mapsto F_{q^n}$$ $$\varphi(a_0,\ldots,a_{n-1}) \mapsto \sum_{i=0}^{n-1}a_ix^i$$
Ahora, para establecer una relación entre matrices invertibles sobre $F_q$ y polinomios de permutación linealizados sobre $F_{q^n}$, debemos definir el mapa $\phi$ que envía un polinomio linealizado $p(X)$ a una matriz invertible $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)))\}$$
Claramente, ambos mapas son lineales y coinciden en la misma imagen aplicando $\varphi$ a la entrada de $p(X)$ y $\varphi^{-1}$ a su salida.
$$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 términos de informática, no necesita calcular polinomios de permutación lineal, sino que puede trabajar con matrices cuadradas invertibles sobre un campo principal o un campo de extensión de dicho campo. ¿Por qué? Bueno, se ha demostrado que los polinomios de permutación lineal$F_{q^n}$ y Matrices Invertibles sobre $F_q$definir una acción equivalente por la relación expuesta anteriormente. Estas matrices son elementos del grupo lineal general$GL_n(q)$. Esta definición, garantiza que, dada una matriz invertible$M$ encima $F_q$, la operacion $M \cdot x = b$ permuta $x$. Como consecuencia, aquí la multiplicación define una biyección sobre el conjunto de elementos de$F_q$.
Hay más trabajo en la rama de combinatoria. Por ejemplo, el grupo simétrico en$n$ simbolos $S_n$ se compone de todas las permutaciones de grado $n$. A partir de aquí, puede calcular el$k$la permutación de un conjunto $S$ teniendo $n$ elementos por la descomposición en el sistema numérico factorádico, que le da una lista de cocientes que define que $k$la permutación. Otro punto, es el que mencionaste, que se basa en la exponenciación modular. Por eso, entienda que tener un pedido grande$r$ S t $g^r \equiv_p 1$ está satisfecho, es bastante poco práctico para las permutaciones, ya que debe calcular cada imagen $g^i$ hasta $g^r$, que está limitada por la longitud de su conjunto $S$ que se va a permutar.