Parametrisierte Permutationsfunktion
Ich suche nach einer Möglichkeit, eine Funktion zu konstruieren, die wie im folgenden Bild dargestellt funktioniert:
Das heißt, ich möchte, dass die Elemente in einem bestimmten Array permutiert werden , um sie in einer anderen Reihenfolge zu platzieren, abhängig von einem Parameter, den ich ihm gebe, damit die Nummern meiner Wahl aus dem ursprünglichen Satz (die ich mit grauem Hintergrund markiert habe) alle endet als kontinuierlicher Bereich am Anfang des Ausgabearrays (links von der dicken Linie), während alle anderen Elemente (roter Hintergrund) an den verbleibenden Positionen in diesem Array (rechts von der dicken Linie) enden würden. .
Die Reihenfolge dieser Elemente in jedem der Ausgabebereiche (grau oder rot) spielt für mich keine Rolle. Sie können von dieser Funktion in eine beliebige Reihenfolge gebracht werden, unabhängig davon, was für eine bestimmte Auswahl ausgewählter Eingabeelemente (grau) einfacher zu berechnen ist. Das einzige, was zählt, ist, dass alle ausgewählten Elemente (grau) auf einer Seite der Grenze landen, während andere Elemente (rot) auf der anderen Seite dieser Grenze landen und die beiden Bereiche durchgehend sind.
Diese Funktion muss parametrierbar sein, damit ich aus allen möglichen Permutationen dieses Arrays die bestimmte Permutation auswählen kann, die die Elemente in diese bestimmte Reihenfolge bringt, indem ich nur einige numerische Parameter (oder Parameter) in der Formel der Funktion spezifiziere.
Ein numerischer Parameter ist vorzuziehen, da es nur eine Permutation gibt, die alle Elemente in diese bestimmte Reihenfolge bringt, und diese Nummer könnte die "Identifikationsnummer" dieser Permutation sein, aber wenn dies schwer zu erreichen wäre, sind mehrere numerische Parameter akzeptabel , solange es die Anzahl der ausgewählten Elemente nicht überschreitet (was es wahrscheinlich sowieso nicht wert wäre).
Gibt es eine Möglichkeit, eine Formel für eine solche Funktion systematisch zu erstellen, wenn eine Teilmenge "ausgewählter Elemente" aus dem Eingabearray gegeben ist? Vielleicht etwas, das auf modularer Arithmetik oder endlichen Feldern basiert? Eine schnelle Websuche gab mir einen Begriff namens "Permutationspolynome", der auf den ersten Blick irgendwie mit diesem Problem zu tun zu haben scheint, aber alle Ressourcen, die ich über sie finden konnte, sind eine dicke Mathematik, die viel Hintergrund in diesem Bereich zu erfordern scheint um überhaupt zu verstehen, was los ist (Ich bin nur ein IT-Ingenieur / Programmierer, der nach einer Lösung für ein Programmierproblem sucht, kein professioneller Mathematiker: q)
Natürlich kann jede Funktion in eine Nachschlagetabelle gestellt werden. Aber das ist nicht das, wonach ich suche, denn das würde eine Nachschlagetabelle von der gleichen Größe wie der gesamte Eingabesatz erfordern, was ein Overkill wäre.
Bearbeiten:
Eine Sache, die mir in den Sinn kommt, ist die modulare Exponentiation, da in Primmodulen eine primitive Wurzel als Basis gewählt wird und der Exponent unsere ist$x$Dann ist jede Potenz dieser Basis einzigartig (maximale Periode) und die resultierende Sequenz ist eine Permutation der ursprünglichen Sequenz (sie beginnt und endet jedoch immer mit 1 und es gibt immer eine $N-1$mitten drin). Aber auf diese Weise kann ich nur einige Permutationen erhalten, nicht jede mögliche Permutation.
Erhöhen dieser Exponentialfunktion auf eine andere Kraft$p$ wählt nur jeden aus $p$th Element aus dieser Sequenz, so kann ich auf diese Weise nur eine Sequenz für eine andere primitive Wurzel erhalten (vorausgesetzt, dass $p$ist Koprime auf die Größe des Moduls kleiner als eins, weil sonst die Periode in kürzere Zyklen zerfällt, wie bei einer anderen Basis, die keine primitive Wurzel ist). Vielleicht gibt es eine andere Möglichkeit, diese Zahlen zu mischen als die Potenzierung?
Antworten
Wie Sie vielleicht wissen, ein invertierbares (nicht singuläres) $n\times n$ Matrix mit Einträgen über $F_q$, wobei q =$p^k$ und $p$ prime definiert einen endlichen Bildraum, also eine Permutation von $F_q^n$. Dies ist gegeben$M \in GL_n(q)$ wo $q=p^k$ und $k\geq 1$, wie $M$ ist nicht singulär, es definiert eine Permutation über die Tupel in $F_q^n$. Dies ist eine Folge von$M$ ein Element der allgemeinen linearen Gruppe (invertierbare Matrizen) zu sein und die Matrixmultiplikation modulo reduziert zu sein $p$ oder $f(x)$ wenn $F_q$ Es ist ein Erweiterungsfeld $n$.
Sie haben Permutationspolynome über endlichen Feldern erwähnt, die Folgendes enthalten $q$Elemente. Es ergibt sich, dass die Gruppe der linearisierten Permutationspolynome vorbei ist$F_{q^n}$ unter Zusammensetzung und die Gruppe der invertierbaren Matrizen über $F_q$unter Multiplikation sind isomorph. Ein linearisiertes Polynom vorbei$F_{q^n}$ kann definiert werden als $p(X) = \sum_{i=0}^{n-1} \alpha_i x^{q^i} \; \alpha_i \in F_{q^n}$ und wir haben einige mathematische Möglichkeiten, um zu beweisen, ob es sich um ein Permutationspolynom handelt oder nicht.
Erklären Sie zunächst die Beziehung zwischen Gradpolynomen $n-1$ Über $F_q$ und Vektortupel vorbei $F_q$ der Dimension $n$. Die Karte$\varphi$ sendet einen Vektor an ein Polynom und umgekehrt:
$$\varphi : F_q^n \mapsto F_{q^n}$$ $$\varphi(a_0,\ldots,a_{n-1}) \mapsto \sum_{i=0}^{n-1}a_ix^i$$
Nun, um eine Beziehung zwischen invertierbaren Matrizen über herzustellen $F_q$ und linearisierte Permutationspolynome über $F_{q^n}$müssen wir die Karte definieren $\phi$ das sendet ein linearisiertes Polynom $p(X)$ zu einer invertierbaren Matrix $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)))\}$$
Beide Karten sind eindeutig linear und stimmen durch Anwenden auf dasselbe Bild überein $\varphi$ zum Eingang von $p(X)$ und $\varphi^{-1}$ zu seiner Ausgabe.
$$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 Bezug auf die Informatik müssen Sie keine linearisierten Permutationspolynome berechnen, sondern können mit invertierbaren quadratischen Matrizen über einem Primfeld oder einem Erweiterungsfeld eines solchen Feldes arbeiten. Warum? Nun, es wurde bewiesen, dass linearisierte Permutationspolynome vorbei sind$F_{q^n}$ und invertierbare Matrizen vorbei $F_q$Definieren Sie eine äquivalente Aktion durch die oben dargestellte Beziehung. Diese Matrizen sind Elemente der allgemeinen linearen Gruppe$GL_n(q)$. Diese Definition garantiert dies bei einer invertierbaren Matrix$M$ Über $F_q$, die Operation $M \cdot x = b$ permutiert $x$. Infolgedessen definiert die Multiplikation hier eine Bijektion auf die Menge der Elemente von$F_q$.
Es gibt mehr Arbeit im Bereich der Kombinatorik. Zum Beispiel die symmetrische Gruppe an$n$ Symbole $S_n$ besteht aus allen Gradpermutationen $n$. Von hier aus können Sie die berechnen$k$th Permutation einer Menge $S$ haben $n$ Elemente durch die Zerlegung in das Factoradic Number System, das Ihnen eine Quotientenliste gibt, die dies definiert $k$th Permutation. Ein weiterer Punkt ist der von Ihnen erwähnte, der auf modularer Exponentiation basiert. Verstehe dafür, dass du einen großen Auftrag hast$r$ st $g^r \equiv_p 1$ ist zufrieden, es ist ziemlich unpraktisch für Permutationen, da Sie jedes Bild berechnen müssen $g^i$ bis um $g^r$, die durch die Länge Ihres Sets begrenzt ist $S$ das wird permutiert.