매개 변수화 된 순열 함수
다음 그림에 묘사 된 방식으로 작동하는 함수를 구성하는 방법을 찾고 있습니다.
그게 내가 그것을 할,이다 뒤 바꿔 일부에 넣어하기 위해 지정된 배열의 요소를 다른 순서 에 따라 매개 변수 그래서 원래 세트 (회색 배경으로 표시하는 I)에서 내 선택의 숫자가 모든 것, 나는 그것을 제공 출력 배열의 시작 부분 (굵은 선의 왼쪽)에서 연속 범위로 끝나는 반면, 다른 모든 요소 (빨간색 배경)는 해당 배열의 나머지 위치 (굵은 선의 오른쪽)에서 끝납니다. .
각 출력 범위 (회색 또는 빨간색)에서 해당 요소의 순서는 나에게 중요하지 않습니다. 선택한 입력 요소 (회색)의 특정 선택에 대해 계산하는 것이 더 간단한 함수에 따라 임의의 순서로 배치 할 수 있습니다. 중요한 것은 선택된 모든 요소 (회색)가 경계의 한 쪽에서 끝나고 다른 요소 (빨간색)가 해당 경계의 다른 쪽에서 끝나고 두 범위가 연속적이라는 것입니다.
이 함수 는이 배열의 가능한 모든 순열 중에서 함수의 공식에 숫자 매개 변수 (또는 매개 변수)를 지정하여 요소를 특정 순서로 배치하는 특정 순열을 선택할 수 있도록 매개 변수화 할 수 있어야합니다.
모든 요소를이 특정 순서로 배치하는 순열이 하나 뿐이고이 순열의 "식별 번호"가 될 수 있기 때문에 하나의 숫자 매개 변수가 바람직하지만 달성하기 어려운 경우 여러 숫자 매개 변수가 허용됩니다. , 선택한 요소의 수를 초과하지 않는 한 (어쨌든 노력할 가치가 없을 것입니다).
입력 배열에서 "선택된 요소"의 하위 집합을 고려하여 이러한 함수에 대한 공식을 체계적으로 구성하는 방법이 있습니까? 모듈 식 산술이나 유한 필드에 기반한 것일까 요? 빠른 웹 검색을 통해 "순열 다항식"이라는 용어가 생겼는데, 언뜻보기에는이 문제와 관련이있는 것처럼 보이지만 이에 대해 찾을 수있는 모든 리소스는 해당 분야에 대한 많은 배경 지식이 필요한 것처럼 보이는 두꺼운 수학입니다. 무슨 일이 일어나고 있는지 이해하기 위해 (저는 전문 수학자가 아닌 일부 프로그래밍 문제에 대한 해결책을 찾고있는 IT 엔지니어 / 프로그래머입니다 : q)
물론 모든 함수를 조회 테이블에 넣을 수 있습니다. 그러나 그것은 전체 입력 세트와 동일한 크기의 조회 테이블이 필요하기 때문에 내가 찾고있는 것이 아닙니다.
편집 :
내 마음에 떠오르는 한 가지는 모듈 식 지수입니다. 왜냐하면 소수 모듈에서 원시 루트가 기본으로 선택되고 지수가 우리의$x$, 그러면 해당 염기의 모든 거듭 제곱은 고유하며 (최대 기간) 결과 시퀀스는 원래 시퀀스의 일부 순열입니다 (그러나 항상 1로 시작하고 끝나며 항상 $N-1$중간에). 그러나 이렇게하면 가능한 모든 순열이 아닌 일부 순열 만 얻을 수 있습니다 . 이 지수 함수를 다른 거듭 제곱으로 올리기
$p$ 모든 항목 만 선택 $p$이 시퀀스의 요소이므로 이렇게하면 다른 원시 루트에 대한 시퀀스 만 가져올 수 있습니다. $p$그렇지 않으면 원시 루트가 아닌 다른 염기와 같이주기가 더 짧은 주기로 나뉘 기 때문입니다). 지수화보다 숫자를 섞는 다른 방법이 있을까요?
답변
아시다시피 반 전형 (비단 수) $n\times n$ 항목이있는 행렬 $F_q$, 여기서 q =$p^k$ 과 $p$ 소수는 유한 한 이미지 공간을 정의하므로 $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$ 요소를 Factoradic Number System으로 분해하여이를 정의하는 몫 목록을 제공합니다. $k$th 순열. 또 다른 요점은 모듈 식 지수를 기반으로하는 언급 한 것입니다. 이를 위해 큰 주문이$r$ 성 $g^r \equiv_p 1$ 각 이미지를 계산해야하므로 순열에 대해서는 매우 실용적이지 않습니다. $g^i$ ...까지 $g^r$, 세트의 길이에 의해 제한됨 $S$ 순열 될 것입니다.