Hàm hoán vị tham số
Tôi đang tìm cách tạo một hàm hoạt động theo cách được mô tả trong hình sau:
Đó là, tôi muốn nó hoán vị các phần tử trong một mảng nhất định để đặt chúng theo một số thứ tự khác nhau tùy thuộc vào tham số tôi cung cấp cho nó, sao cho các số tôi chọn từ tập hợp ban đầu (những số tôi đã đánh dấu bằng nền xám) sẽ tất cả kết thúc dưới dạng một phạm vi liên tục ở đầu mảng đầu ra (ở bên trái của dòng dày), trong khi tất cả các phần tử khác (nền đỏ) sẽ kết thúc ở các vị trí còn lại trong mảng đó (ở bên phải của dòng dày) .
Thứ tự của các phần tử đó trong mỗi phạm vi đầu ra (xám hoặc đỏ) không quan trọng đối với tôi. Chúng có thể được đặt theo bất kỳ thứ tự tùy ý nào bởi hàm đó, bất kỳ thứ gì đơn giản hơn để tính toán cho một lựa chọn cụ thể của các phần tử đầu vào đã chọn (màu xám). Điều duy nhất quan trọng là tất cả các phần tử đã chọn đó (màu xám) kết thúc ở một bên của ranh giới, trong khi các phần tử khác (màu đỏ) kết thúc ở phía bên kia của ranh giới đó và hai phạm vi là liên tục.
Hàm này cần phải được tham số hóa để, trong số tất cả các hoán vị có thể có của mảng này, tôi có thể chọn hoán vị cụ thể đó để đặt các phần tử theo thứ tự cụ thể đó bằng cách chỉ định một số tham số (hoặc tham số) trong công thức của hàm.
Tốt hơn là một tham số số, vì chỉ có một hoán vị đặt tất cả các phần tử theo thứ tự cụ thể này và số này có thể là "số nhận dạng" của hoán vị đó, nhưng nếu điều đó khó đạt được, thì một số tham số số có thể chấp nhận được , miễn là nó không vượt quá số phần tử đã chọn (dù sao thì có lẽ sẽ khiến nó không đáng để nỗ lực).
Có cách nào để xây dựng công thức cho một hàm như vậy một cách có hệ thống, cho trước một tập con "các phần tử được chọn" từ mảng đầu vào không? Có thể một cái gì đó dựa trên số học mô-đun hoặc trường hữu hạn? Một tìm kiếm nhanh trên web đã cho tôi một thuật ngữ gọi là "đa thức hoán vị" thoạt nhìn có vẻ như có liên quan đến vấn đề này bằng cách nào đó, nhưng tất cả các tài nguyên tôi có thể tìm thấy về chúng đều là một số phép toán dày đặc mà dường như đòi hỏi rất nhiều kiến thức về lĩnh vực đó thậm chí hiểu những gì đang xảy ra (Tôi chỉ là một kỹ sư CNTT / lập trình viên đang tìm kiếm giải pháp cho một số vấn đề lập trình, không phải là một nhà toán học chuyên nghiệp: q)
Tất nhiên, bất kỳ chức năng nào cũng có thể được đưa vào một bảng tra cứu. Nhưng đó không phải là những gì tôi đang tìm kiếm, bởi vì điều đó sẽ yêu cầu một bảng tra cứu có cùng kích thước với toàn bộ tập hợp đầu vào, điều này sẽ là quá mức cần thiết.
Chỉnh sửa:
Một điều xuất hiện trong đầu tôi là lũy thừa mô-đun, vì trong moduli nguyên tố, khi một gốc nguyên thủy được chọn làm cơ sở và số mũ là của chúng ta$x$, thì mọi lũy thừa của cơ số đó là duy nhất (chu kỳ cực đại) và chuỗi kết quả là một số hoán vị của chuỗi ban đầu (tuy nhiên, nó luôn bắt đầu và kết thúc bằng 1 và luôn có $N-1$ở giữa). Nhưng bằng cách này, tôi chỉ có thể nhận được một số hoán vị, không phải mọi hoán vị có thể .
Nâng cấp hàm mũ này thành một số lũy thừa khác$p$ chỉ chọn mỗi $p$phần tử thứ từ trình tự này, vì vậy theo cách này, tôi chỉ có thể lấy một trình tự cho một gốc nguyên thủy khác (miễn là $p$là coprime với kích thước của môđun nhỏ hơn một, bởi vì nếu không thì chu kỳ sẽ chia thành các chu kỳ ngắn hơn, giống như đối với một số cơ sở khác không phải là gốc nguyên thủy). Có thể có một số cách khác để xáo trộn những con số đó ngoài phép tính lũy thừa?
Trả lời
Như bạn có thể biết, không thể đảo ngược (không phải số ít) $n\times n$ ma trận có các mục nhập hơn $F_q$, trong đó q =$p^k$ và $p$ số nguyên tố định nghĩa một không gian hình ảnh hữu hạn, do đó nó là một hoán vị của $F_q^n$. Đây là, đã cho$M \in GL_n(q)$ Ở đâu $q=p^k$ và $k\geq 1$, như $M$ không phải là số ít, nó xác định một hoán vị trên các bộ giá trị trong $F_q^n$. Đây là hệ quả của$M$ là một phần tử của nhóm tuyến tính tổng quát (ma trận khả nghịch) và phép nhân ma trận được giảm mô đun $p$ hoặc là $f(x)$ nếu $F_q$ nó là một trường mở rộng của mức độ $n$.
Bạn đã đề cập đến Đa thức hoán vị trên Trường hữu hạn chứa $q$các yếu tố. Nó là kết quả mà các nhóm linearised hoán vị đa thức trên$F_{q^n}$ theo thành phần và nhóm các Ma trận khả nghịch $F_q$dưới phép nhân là các phép đồng phân. Đa thức tuyến tính trên$F_{q^n}$ có thể được định nghĩa là $p(X) = \sum_{i=0}^{n-1} \alpha_i x^{q^i} \; \alpha_i \in F_{q^n}$ và chúng tôi có một số cách toán học để chứng minh đó có phải là Đa thức hoán vị hay không.
Đầu tiên, giải thích mối quan hệ giữa các đa thức bậc $n-1$ kết thúc $F_q$ và vectors-tuples qua $F_q$ của chiều $n$. Bản đô$\varphi$ gửi một vectơ đến một đa thức và ngược lại:
$$\varphi : F_q^n \mapsto F_{q^n}$$ $$\varphi(a_0,\ldots,a_{n-1}) \mapsto \sum_{i=0}^{n-1}a_ix^i$$
Bây giờ, để thiết lập mối quan hệ giữa các ma trận khả nghịch qua $F_q$ và Đa thức hoán vị tuyến tính trên $F_{q^n}$, chúng ta phải xác định bản đồ $\phi$ gửi một Đa thức tuyến tính $p(X)$ thành một ma trận khả nghịch $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)))\}$$
Rõ ràng, cả hai bản đồ đều tuyến tính và thống nhất trên cùng một hình ảnh bằng cách áp dụng $\varphi$ đầu vào của $p(X)$ và $\varphi^{-1}$ đến đầu ra của nó.
$$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)))$$
Về mặt khoa học máy tính, bạn không cần phải tính Đa thức hoán vị tuyến tính, thay vào đó, bạn có thể làm việc với ma trận vuông khả nghịch trên một trường nguyên tố hoặc một trường mở rộng của trường đó. Tại sao? Chà, người ta đã chứng minh rằng Đa thức hoán vị tuyến tính qua$F_{q^n}$ và Ma trận khả nghịch qua $F_q$xác định một hành động tương đương bằng mối quan hệ được trình bày ở trên. Các ma trận này là phần tử của nhóm tuyến tính tổng quát$GL_n(q)$. Định nghĩa này đảm bảo rằng, đưa ra một ma trận khả nghịch$M$ kết thúc $F_q$, hoạt động $M \cdot x = b$ hoán vị $x$. Do đó, ở đây phép nhân xác định một phép nhân đôi trên tập hợp các phần tử của$F_q$.
Có nhiều công việc hơn thuộc nhánh tổ hợp. Ví dụ, nhóm đối xứng trên$n$ ký hiệu $S_n$ bao gồm tất cả các hoán vị của mức độ $n$. Từ đây, bạn có thể tính toán$k$hoán vị thứ của một tập hợp $S$ đang có $n$ các phần tử bằng cách phân tách thành Hệ thống số thừa, cung cấp cho bạn một danh sách thương số xác định rằng $k$hoán vị thứ. Một điểm khác, là một trong những bạn đã đề cập, được dựa trên lũy thừa mô-đun. Vì vậy, hãy hiểu rằng có một đơn đặt hàng lớn$r$ st $g^r \equiv_p 1$ hài lòng rằng nó khá không thực tế cho các hoán vị, vì bạn phải tính toán từng hình ảnh $g^i$ cho đến khi $g^r$, được giới hạn bởi độ dài của tập hợp của bạn $S$ sẽ được hoán vị.