Fungsi permutasi parameter
Saya mencari cara untuk membuat sebuah fungsi yang akan bekerja seperti yang digambarkan dalam gambar berikut:
Yaitu, saya ingin mengubah elemen dalam array tertentu untuk menempatkannya dalam beberapa urutan berbeda tergantung pada parameter yang saya berikan, sehingga nomor pilihan saya dari set asli (yang saya tandai dengan latar belakang abu-abu) akan semuanya berakhir sebagai rentang kontinu di awal larik keluaran (di sebelah kiri garis tebal), sementara semua elemen lainnya (latar belakang merah) akan berakhir di posisi tersisa dalam larik itu (di sebelah kanan garis tebal) .
Urutan elemen tersebut di setiap rentang keluaran (abu-abu atau merah) tidak masalah bagi saya. Mereka dapat diletakkan dalam urutan sembarang dengan fungsi itu, apa pun yang lebih sederhana untuk dihitung untuk pilihan tertentu dari elemen masukan yang dipilih (abu-abu). Satu-satunya hal yang penting adalah bahwa semua elemen yang dipilih (abu-abu) berakhir di satu sisi batas, sementara elemen lainnya (merah) berakhir di sisi lain dari batas itu, dan kedua rentang tersebut kontinu.
Fungsi ini perlu parametrizable sehingga, dari semua kemungkinan permutasi larik ini, saya dapat memilih permutasi tertentu yang menempatkan elemen dalam urutan tertentu dengan hanya menentukan beberapa parameter numerik (atau parameter) dalam rumus fungsi.
Satu parameter numerik lebih disukai, karena hanya ada satu permutasi yang menempatkan semua elemen dalam urutan tertentu ini, dan angka ini bisa menjadi "nomor identifikasi" dari permutasi tersebut, tetapi jika itu sulit dicapai, beberapa parameter numerik dapat diterima , selama tidak melebihi jumlah elemen yang dipilih (yang mungkin akan membuatnya tidak sebanding dengan usahanya).
Adakah cara untuk membuat rumus untuk fungsi seperti itu secara sistematis, dengan memberikan subset dari "elemen terpilih" dari larik masukan? Mungkin sesuatu yang didasarkan pada aritmatika modular atau bidang terbatas? Pencarian web cepat memberi saya istilah yang disebut "permutasi polinomial" yang pada pandangan pertama tampaknya terkait dengan masalah ini, tetapi semua sumber daya yang dapat saya temukan tentang mereka adalah beberapa matematika tebal yang tampaknya membutuhkan banyak latar belakang di bidang itu bahkan untuk memahami apa yang sedang terjadi (Saya hanya seorang insinyur / programmer TI yang mencari solusi untuk beberapa masalah pemrograman, bukan ahli matematika profesional: q)
Tentu saja, fungsi apa pun dapat dimasukkan ke dalam tabel pemeta. Tapi bukan itu yang saya cari, karena itu akan membutuhkan tabel pencarian dengan ukuran yang sama dengan seluruh set input, yang akan berlebihan.
Sunting:
Satu hal yang terlintas di benak saya adalah eksponensial modular, karena dalam modulus prima, ketika akar primitif dipilih sebagai basis, dan eksponennya adalah milik kami$x$, maka setiap pangkat basis itu unik (periode maksimal) dan urutan yang dihasilkan adalah beberapa permutasi dari urutan aslinya (namun, selalu dimulai dan diakhiri dengan 1, dan selalu ada $N-1$di tengah-tengah). Tapi dengan cara ini saya hanya bisa mendapatkan beberapa permutasi, tidak semua permutasi yang mungkin .
Meningkatkan fungsi eksponensial ini ke beberapa pangkat lain$p$ hanya memilih setiap $p$elemen th dari urutan ini, jadi dengan cara ini saya hanya bisa mendapatkan urutan untuk root primitif lain (asalkan $p$adalah coprime dengan ukuran modulus kurang satu, karena jika tidak periode terpecah menjadi siklus yang lebih pendek, seperti untuk beberapa basis lain yang bukan akar primitif). Mungkin ada cara lain untuk mengacak angka-angka itu selain eksponen?
Jawaban
Seperti yang Anda ketahui, sebuah invertible (non-singular) $n\times n$ matriks memiliki entri berakhir $F_q$, dimana q =$p^k$ dan $p$ prime mendefinisikan ruang gambar yang terbatas, jadi itu permutasi $F_q^n$. Ini, diberikan$M \in GL_n(q)$ dimana $q=p^k$ dan $k\geq 1$, sebagai $M$ adalah non-singular, ini mendefinisikan permutasi atas tupel di $F_q^n$. Ini adalah konsekuensi dari$M$ menjadi elemen dari kelompok linier umum (matriks dapat dibalik) dan perkalian matriks yang direduksi modulo $p$ atau $f(x)$ jika $F_q$ itu adalah bidang perluasan gelar $n$.
Anda menyebutkan Permutasi Polinomial di atas Bidang Hingga yang berisi $q$elemen. Hasilnya kelompok Polinomial Permutasi Linearisasi berakhir$F_{q^n}$ di bawah komposisi dan kelompok Matriks yang dapat dibalik selesai $F_q$dalam perkalian bersifat isomorfik. Polinomial Linearisasi berakhir$F_{q^n}$ dapat didefinisikan sebagai $p(X) = \sum_{i=0}^{n-1} \alpha_i x^{q^i} \; \alpha_i \in F_{q^n}$ dan kami memiliki beberapa cara matematika untuk membuktikan apakah itu Permutasi Polinomial atau bukan.
Pertama, jelaskan hubungan antara polinomial derajat $n-1$ lebih $F_q$ dan vektor-tupel berakhir $F_q$ dimensi $n$. Peta$\varphi$ mengirim vektor ke polinomial dan sebaliknya:
$$\varphi : F_q^n \mapsto F_{q^n}$$ $$\varphi(a_0,\ldots,a_{n-1}) \mapsto \sum_{i=0}^{n-1}a_ix^i$$
Sekarang, untuk membangun hubungan antara matriks yang dapat dibalik $F_q$ dan Permutasi Polinomial Linier selesai $F_{q^n}$, kita harus mendefinisikan peta $\phi$ yang mengirimkan Polinomial Linier $p(X)$ ke matriks yang dapat dibalik $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)))\}$$
Jelas, kedua peta itu linier dan menyetujui gambar yang sama dengan menerapkan $\varphi$ ke masukan dari $p(X)$ dan $\varphi^{-1}$ untuk itu keluaran.
$$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)))$$
Dalam hal ilmu komputer, Anda tidak perlu menghitung Polinomial Permutasi Linier, sebagai gantinya, Anda dapat mengerjakan matriks persegi yang dapat dibalik di atas bidang utama, atau bidang ekstensi dari bidang tersebut. Mengapa? Nah, telah dibuktikan bahwa Permutasi Polinomial Linier telah berakhir$F_{q^n}$ dan Matriks Terbalik selesai $F_q$tentukan tindakan yang setara dengan hubungan yang diungkapkan di atas. Matriks ini adalah elemen dari kelompok linier umum$GL_n(q)$. Definisi ini, menjamin itu, mengingat matriks yang dapat dibalik$M$ lebih $F_q$, operasi $M \cdot x = b$ permutes $x$. Sebagai konsekuensinya, perkalian di sini mendefinisikan suatu bijeksi pada himpunan unsur-unsur$F_q$.
Ada lebih banyak pekerjaan di bawah cabang kombinatorik. Misalnya, grup simetris di$n$ simbol $S_n$ terdiri dari semua permutasi derajat $n$. Dari sini, Anda dapat menghitung$k$permutasi dari satu set $S$ memiliki $n$ elemen dengan dekomposisi menjadi Sistem Bilangan Factoradic, yang memberi Anda daftar hasil bagi yang mendefinisikannya $k$permutasi. Poin lain, adalah yang Anda sebutkan, yang didasarkan pada eksponensial modular. Untuk itu, pahamilah bahwa memiliki pesanan besar$r$ st $g^r \equiv_p 1$ puas itu cukup tidak praktis untuk permutasi, karena Anda harus menghitung setiap gambar $g^i$ sampai $g^r$, yang dibatasi oleh panjang perangkat Anda $S$ yang akan diizinkan.