パラメータ化された順列関数
次の図に示すように機能する関数を作成する方法を探しています。
つまり、指定された配列内の要素を並べ替えて、指定したパラメーターに応じて異なる順序で配置し、元のセット（灰色の背景でマークしたもの）から選択した番号がすべてになるようにします。出力配列の先頭（太線の左側）で連続範囲として終了し、他のすべての要素（赤い背景）はその配列の残りの位置（太線の右側）で終了します。 。
各出力範囲（灰色または赤）でのこれらの要素の順序は、私には関係ありません。それらは、選択された入力要素（灰色）の特定の選択に対して計算するのが簡単なものであれば、その関数によって任意の順序で配置できます。重要なのは、選択したすべての要素（灰色）が境界の片側になり、他の要素（赤）が境界の反対側になり、2つの範囲が連続していることだけです。
この関数はパラメーター化可能である必要があります。これにより、この配列のすべての可能な順列から、関数の数式でいくつかの数値パラメーターを指定するだけで、要素を特定の順序に配置する特定の順列を選択できます。
すべての要素をこの特定の順序に並べる順列は1つだけであり、この数はその順列の「識別番号」である可能性があるため、1つの数値パラメーターが望ましいですが、それを達成するのが難しい場合は、いくつかの数値パラメーターを使用できます。 、選択した要素の数を超えない限り（とにかく努力する価値がない可能性があります）。
入力配列から「選択された要素」のサブセットが与えられた場合、そのような関数の式を体系的に構築する方法はありますか？多分、モジュラー算術または有限体に基づく何か？簡単なWeb検索で、「置換多項式」と呼ばれる用語が見つかりました。これは、一見この問題に何らかの形で関連しているように見えますが、それらについて見つけることができるすべてのリソースは、その分野で多くの背景を必要とするような厚い数学です。何が起こっているのかを理解することさえできます（私はプロの数学者ではなく、プログラミングの問題の解決策を探しているITエンジニア/プログラマーです：q）
もちろん、どの関数もルックアップテーブルに入れることができます。しかし、それは私が探しているものではありません。入力セット全体と同じサイズのルックアップテーブルが必要になり、やり過ぎになるからです。
編集：
私の頭に浮かぶことの1つは、べき乗剰余です。原始根が底として選択され、指数が私たちの$x$、その場合、そのベースのすべての累乗は一意であり（最大周期）、結果のシーケンスは元のシーケンスの順列になります（ただし、常に1で開始および終了し、常に $N-1$途中で）。しかし、この方法では、すべての可能な順列ではなく、いくつかの順列しか取得できません。この指数関数を他の累乗に上げる
$p$ すべてを選択するだけ $p$このシーケンスからの要素なので、この方法では、別の原始根のシーケンスしか取得できません（ただし、 $p$は、モジュラスのサイズから1を引いたものと互いに素です。そうでない場合、原始根ではない他のベースのように、周期がより短いサイクルに分割されるためです。べき乗以外に、これらの数値をシャッフルする方法は他にあるでしょうか。
回答
ご存知かもしれませんが、可逆（非特異） $n\times n$ 上のエントリを持つ行列 $F_q$、ここでq =$p^k$ そして $p$ Primeは有限の画像空間を定義するため、次の順列になります。 $F_q^n$。これは、与えられた$M \in GL_n(q)$ どこ $q=p^k$ そして $k\geq 1$、 なので $M$ は非特異であり、のタプルの順列を定義します $F_q^n$。これはの結果です$M$ 一般線形群（可逆行列）の要素であり、行列の乗算はモジュロで削減されます $p$ または $f(x)$ もし $F_q$ それは程度の拡大体です $n$。
を含む有限体上の置換多項式について言及しました $q$要素。その結果、線形化された置換多項式のグループは$F_{q^n}$ 構成と反転可能な行列のグループの下で $F_q$乗算中は同型です。上の線形化された多項式$F_{q^n}$ 次のように定義できます $p(X) = \sum_{i=0}^{n-1} \alpha_i x^{q^i} \; \alpha_i \in F_{q^n}$ そして、それが置換多項式であるかどうかを証明するいくつかの数学的な方法があります。
まず、次数の多項式間の関係を説明します $n-1$ 以上 $F_q$ およびベクトル-タプルオーバー $F_q$ 寸法の $n$。地図$\varphi$ ベクトルを多項式に送信し、その逆も同様です。
$$\varphi : F_q^n \mapsto F_{q^n}$$ $$\varphi(a_0,\ldots,a_{n-1}) \mapsto \sum_{i=0}^{n-1}a_ix^i$$
さて、上の可逆行列間の関係を確立するには $F_q$ および線形化された置換多項式 $F_{q^n}$、マップを定義する必要があります $\phi$ 線形化された多項式を送信します $p(X)$ 可逆行列に $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)))\}$$
明らかに、両方のマップは線形であり、適用することで同じ画像に一致します $\varphi$ の入力に $p(X)$ そして $\varphi^{-1}$ その出力に。
$$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)))$$
コンピュータサイエンスの観点からは、線形化された置換多項式を計算する必要はありません。代わりに、プライムフィールドまたはそのようなフィールドの拡大フィールド上で可逆正方行列を操作できます。どうして？さて、線形化された順列多項式が$F_{q^n}$ および可逆行列 $F_q$上で公開された関係によって同等のアクションを定義します。これらの行列は一般線形群の要素です$GL_n(q)$。この定義は、可逆行列が与えられた場合、それを保証します$M$ 以上 $F_q$、 操作 $M \cdot x = b$ 順列 $x$。結果として、ここでの乗算は、の要素のセットに対する全単射を定義します。$F_q$。
組み合わせ論の分野では、さらに多くの作業があります。たとえば、上の対称群$n$ 記号 $S_n$ 次数のすべての順列で構成されています $n$。ここから、を計算できます$k$セットの順列 $S$ 持っている $n$ 階乗進法への分解による要素。これにより、それを定義する商リストが得られます。 $k$th順列。もう1つのポイントは、べき乗剰余に基づいている、あなたが言及したものです。そのためには、大きな注文があることを理解してください$r$ st $g^r \equiv_p 1$ 各画像を計算する必要があるため、順列にはまったく実用的ではありません。 $g^i$ まで $g^r$、これはセットの長さによって制限されます $S$ これは順列になります。