Funzione di permutazione parametrizzata
Sto cercando un modo per costruire una funzione che funzioni nel modo illustrato nella figura seguente:
Cioè, voglio che permuti gli elementi in un dato array per metterli in un ordine diverso a seconda di un parametro che gli do, in modo che i numeri di mia scelta dal set originale (quelli che ho contrassegnato con sfondo grigio) siano tutti finire come un intervallo continuo all'inizio dell'array di output (a sinistra della linea spessa), mentre tutti gli altri elementi (sfondo rosso) finirebbero nelle posizioni rimanenti in quell'array (a destra della linea spessa) .
L'ordine di quegli elementi in ciascuno degli intervalli di output (grigio o rosso) non ha importanza per me. Possono essere messi in qualsiasi ordine arbitrario da quella funzione, qualunque cosa sia più semplice da calcolare per una particolare scelta di elementi di input selezionati (grigio). L'unica cosa che conta è che tutti quegli elementi selezionati (grigi) finiscano su un lato del confine, mentre altri elementi (rossi) finiscano sull'altro lato di quel confine, e i due intervalli sono continui.
Questa funzione deve essere parametrizzabile in modo che, tra tutte le possibili permutazioni di questo array, potrei scegliere quella particolare permutazione che mette gli elementi in quel particolare ordine semplicemente specificando alcuni parametri numerici (o parametri) nella formula della funzione.
È preferibile un parametro numerico, poiché esiste una sola permutazione che mette tutti gli elementi in questo particolare ordine, e questo numero potrebbe essere il "numero identificativo" di quella permutazione, ma se ciò fosse difficile da ottenere, diversi parametri numerici sono accettabili , purché non superi il numero di elementi scelti (il che probabilmente non ne vale comunque la pena).
C'è un modo per costruire una formula per tale funzione in modo sistematico, dato un sottoinsieme di "elementi scelti" dall'array di input? Forse qualcosa basato su aritmetica modulare o campi finiti? Una rapida ricerca sul Web mi ha dato un termine chiamato "polinomi di permutazione" che a prima vista sembra essere in qualche modo correlato a questo problema, ma tutte le risorse che ho potuto trovare su di essi sono una matematica densa che sembra richiedere molto background in quel campo per capire anche cosa sta succedendo (sono solo un ingegnere informatico / programmatore alla ricerca di una soluzione per qualche problema di programmazione, non un matematico professionista: q)
Naturalmente, qualsiasi funzione potrebbe essere inserita in una tabella di ricerca. Ma non è quello che sto cercando, perché richiederebbe una tabella di ricerca delle stesse dimensioni dell'intero set di input, il che sarebbe eccessivo.
Modifica:
una cosa che mi viene in mente è l'elevamento a potenza modulare, poiché nei moduli primi, quando una radice primitiva viene scelta come base e l'esponente è il nostro$x$, allora ogni potenza di quella base è unica (periodo massimo) e la sequenza risultante è una permutazione della sequenza originale (tuttavia, inizia e finisce sempre con 1, e c'è sempre$N-1$nel mezzo). Ma in questo modo posso ottenere solo alcune permutazioni, non tutte le possibili permutazioni.
Elevare questa funzione esponenziale a qualche altra potenza$p$seleziona solo ogni$p$esimo elemento da questa sequenza, quindi in questo modo posso ottenere solo una sequenza per un'altra radice primitiva (a condizione che$p$è coprimo alla dimensione del modulo meno uno, perché altrimenti il periodo si spezza in cicli più brevi, come per qualche altra base che non sia una radice primitiva). Forse c'è un altro modo per mescolare quei numeri oltre all'elevazione a potenza?
Risposte
Come forse saprai, un invertibile (non singolare)$n\times n$matrice con voci sopra$F_q$, dove q=$p^k$e$p$prime definisce uno spazio immagine finito, quindi è una permutazione di$F_q^n$. Questo è dato$M \in GL_n(q)$dove$q=p^k$e$k\geq 1$, come$M$è non singolare, definisce una permutazione sulle tuple in$F_q^n$. Questa è una conseguenza di$M$essendo un elemento del gruppo lineare generale (matrici invertibili) e la moltiplicazione di matrici essendo modulo ridotto$p$o$f(x)$Se$F_q$è un campo di estensione del grado$n$.
Hai menzionato i polinomi di permutazione su campi finiti contenenti$q$elementi. Ne risulta che il gruppo dei Polinomi di Permutazione Linearizzati è finito$F_{q^n}$sotto composizione e sopra il gruppo delle Matrici invertibili$F_q$sotto la moltiplicazione sono isomorfe. Un polinomio linearizzato finito$F_{q^n}$può essere definito come$p(X) = \sum_{i=0}^{n-1} \alpha_i x^{q^i} \; \alpha_i \in F_{q^n}$e abbiamo alcuni modi matematici per dimostrare se si tratta di un polinomio di permutazione o meno.
Innanzitutto, spiega la relazione tra polinomi di grado$n-1$Sopra$F_q$e vettori-tuple sopra$F_q$di dimensione$n$. La mappa$\varphi$invia un vettore a un polinomio e 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$$
Ora, per stabilire una relazione tra matrici invertibili finita$F_q$e polinomi di permutazione linearizzati sopra$F_{q^n}$, dobbiamo definire la mappa$\phi$che invia un polinomio linearizzato$p(X)$ad una matrice invertibile$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)))\}$$
Chiaramente, entrambe le mappe sono lineari e concordano sulla stessa immagine applicando$\varphi$all'ingresso di$p(X)$e$\varphi^{-1}$alla sua uscita.
$$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)))$$
In termini di informatica, non è necessario calcolare i polinomi di permutazione linearizzati, ma è possibile lavorare con matrici quadrate invertibili su un campo primo o su un campo di estensione di tale campo. Come mai? Bene, è stato dimostrato che i polinomi di permutazione linearizzati sono finiti$F_{q^n}$e Matrici Invertibili oltre$F_q$definire un'azione equivalente dalla relazione esposta sopra. Queste matrici sono elementi del gruppo lineare generale$GL_n(q)$. Questa definizione, garantisce che, data una matrice invertibile$M$Sopra$F_q$, l'operazione$M \cdot x = b$permuta$x$. Di conseguenza, qui la moltiplicazione definisce una biiezione sull'insieme degli elementi di$F_q$.
C'è più lavoro sotto il ramo della combinatoria. Ad esempio, il gruppo simmetrico su$n$simboli$S_n$comprende tutte le permutazioni di grado$n$. Da qui, puoi calcolare il$k$esima permutazione di un insieme$S$avendo$n$elementi mediante la scomposizione nel sistema numerico fattoriale, che fornisce un elenco di quozienti che lo definisce$k$esima permutazione. Un altro punto, è quello che hai citato, che si basa sull'elevamento a potenza modulare. Per questo, capisci che avere un grosso ordine$r$st$g^r \equiv_p 1$è soddisfatto è abbastanza poco pratico per le permutazioni, dal momento che devi calcolare ogni immagine$g^i$Fino a$g^r$, che è delimitato dalla lunghezza del tuo set$S$che sta per essere permutato.