Parametreli permütasyon işlevi
Aşağıdaki resimde gösterildiği gibi çalışacak bir işlev oluşturmanın bir yolunu arıyorum:
Yani ben istiyorum olduğunu permute bazı koymak için belirli bir dizide elemanları farklı sırayla bir bağlı parametre böylece orijinal seti (gri arka plan ile işaretlenmiş I) benim seçim sayılar tüm olur, bunu vermek çıktı dizisinin başlangıcında (kalın çizginin solunda) sürekli bir aralık olarak sonlanırken, diğer tüm öğeler (kırmızı arka plan) o dizideki kalan konumlarda (kalın çizginin sağında) sona erer. .
Çıktı aralıklarının her birinde (gri veya kırmızı) bu öğelerin sırası benim için önemli değil. Seçilen giriş öğelerinin (gri) belirli bir seçimi için hesaplaması daha basit olan, bu işlev tarafından herhangi bir rasgele sıraya konulabilirler. Önemli olan tek şey, seçilen tüm öğelerin (gri) sınırın bir tarafında sona ermesi, diğer öğelerin (kırmızı) bu sınırın diğer tarafında sona ermesi ve iki aralığın sürekli olmasıdır.
Bu işlevin parametreleştirilebilir olması gerekir, böylece bu dizinin tüm olası permütasyonlarından, yalnızca işlevin formülünde bazı sayısal parametreler (veya parametreler) belirterek öğeleri o belirli sıraya koyan belirli permütasyonu seçebilirim.
Bir sayısal parametre tercih edilir, çünkü tüm elemanları bu özel sıraya koyan tek bir permütasyon vardır ve bu sayı, bu permütasyonun "tanımlayıcı numarası" olabilir, ancak bunu başarmak zor olacaksa, birkaç sayısal parametre kabul edilebilir. , seçilen öğelerin sayısını aşmadığı sürece (ki bu muhtemelen zaten çabaya değmez).
Giriş dizisinden "seçilen elemanların" bir alt kümesi verildiğinde, bu tür bir işlev için sistematik bir şekilde formül oluşturmanın bir yolu var mı? Belki modüler aritmetik veya sonlu alanlara dayalı bir şey? Hızlı bir web araması bana "permütasyon polinomları" adı verilen ve ilk bakışta bir şekilde bu problemle ilişkili gibi görünen bir terim verdi, ancak onlar hakkında bulabildiğim tüm kaynaklar, bu alanda çok fazla arka plan gerektiriyor gibi görünen kalın bir matematik. neler olup bittiğini bile anlamak için (Ben profesyonel bir matematikçi değil, bazı programlama problemleri için bir çözüm arayan bir BT mühendisi / programcısıyım: q)
Elbette, herhangi bir işlev bir arama tablosuna yerleştirilebilir. Ama aradığım şey bu değil, çünkü bu, tüm girdi kümesiyle aynı boyutta bir arama tablosu gerektirecek ve bu da bir abartı olacaktır.
Düzenleme:
Aklıma gelen bir şey modüler üs alma, çünkü asal modülde, temel olarak ilkel bir kök seçildiğinde ve üs bizim$x$, o zaman bu tabanın her kuvveti benzersizdir (maksimum nokta) ve ortaya çıkan sıra, orijinal dizinin bir miktar permütasyonudur (ancak, her zaman 1 ile başlar ve biter ve her zaman vardır $N-1$ortada). Ancak bu şekilde , her olası permütasyonu değil , yalnızca bazı permütasyonları elde edebilirim . Bu üstel işlevi başka bir güce yükseltmek
$p$ sadece her birini seçer $p$Bu diziden inci öğesi, dolayısıyla bu şekilde yalnızca başka bir ilkel kök için bir dizi elde edebilirim (şartıyla $p$modülün boyutuna eşittir, çünkü aksi takdirde süre, ilkel kök olmayan diğer bazı bazlar için olduğu gibi daha kısa döngülere girer). Belki de bu sayıları karıştırmanın üsselleştirmeden başka bir yolu vardır?
Yanıtlar
Bildiğiniz gibi, tersinir (tekil olmayan) $n\times n$ üzerinde girişleri olan matris $F_q$, burada q =$p^k$ ve $p$ asal, sonlu bir görüntü uzayını tanımlar, dolayısıyla bir permütasyondur. $F_q^n$. Bu verildi$M \in GL_n(q)$ nerede $q=p^k$ ve $k\geq 1$, gibi $M$ tekil değildir, içindeki tuples üzerinde bir permütasyon tanımlar $F_q^n$. Bu bir sonucudur$M$ Genel doğrusal grubun (ters çevrilebilir matrisler) bir öğesi olmak ve matris çarpımı indirgenmiş modulo $p$ veya $f(x)$ Eğer $F_q$ bu bir derece alanı $n$.
Permütasyon Polinomlarını içeren Sonlu Alanlar yerine $q$elementler. Doğrusal Permütasyon Polinomları grubunun$F_{q^n}$ kompozisyon altında ve ters çevrilebilir Matrisler grubu altında $F_q$çarpma altında izomorfiktir. Üzerinde Doğrusal Polinom$F_{q^n}$ olarak tanımlanabilir $p(X) = \sum_{i=0}^{n-1} \alpha_i x^{q^i} \; \alpha_i \in F_{q^n}$ ve bunun bir Permütasyon Polinomu olup olmadığını kanıtlamak için bazı matematiksel yollarımız var.
İlk olarak, derece polinomları arasındaki ilişkiyi açıklayın $n-1$ bitmiş $F_q$ ve vektörler-tuples bitti $F_q$ boyut $n$. Harita$\varphi$ bir polinoma bir vektör gönderir ve bunun tersi de geçerlidir:
$$\varphi : F_q^n \mapsto F_{q^n}$$ $$\varphi(a_0,\ldots,a_{n-1}) \mapsto \sum_{i=0}^{n-1}a_ix^i$$
Şimdi, ters çevrilebilir matrisler arasında bir ilişki kurmak için $F_q$ ve Doğrusal Permütasyon Polinomları $F_{q^n}$haritayı tanımlamalıyız $\phi$ Doğrusal Polinom gönderen $p(X)$ tersinir bir matrise $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)))\}$$
Açıkça, her iki harita da doğrusaldır ve uygulayarak aynı görüntü üzerinde anlaşırlar. $\varphi$ girişine $p(X)$ ve $\varphi^{-1}$ çıkışına.
$$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)))$$
Bilgisayar bilimi açısından, Doğrusal Permütasyon Polinomlarını hesaplamanıza gerek yoktur, bunun yerine tersinir kare matrislerle bir asal alan veya böyle bir alanın bir uzantı alanı üzerinde çalışabilirsiniz. Neden? Doğrusallaştırılmış Permütasyon Polinomlarının$F_{q^n}$ ve Ters Çevrilebilir Matrisler $F_q$Yukarıda ortaya konan ilişkiyle eşdeğer bir eylem tanımlayın. Bu matrisler, genel doğrusal grubun öğeleridir$GL_n(q)$. Bu tanım, tersinir bir matris verildiğinde,$M$ bitmiş $F_q$, operasyon $M \cdot x = b$ permüteler $x$. Sonuç olarak, burada çarpma, aşağıdaki unsurlar kümesi üzerinde bir eşleştirme tanımlar.$F_q$.
Kombinatorik dalında daha çok iş var. Örneğin, simetrik grup$n$ semboller $S_n$ derecenin tüm permütasyonlarından oluşur $n$. Buradan hesaplayabilirsiniz.$k$bir kümenin inci permütasyonu $S$ sahip olmak $n$ Faktöradik Sayı Sistemine ayrıştırılarak elemanlar, bu size bunu tanımlayan bir bölüm listesi verir. $k$inci permütasyon. Diğer bir nokta, modüler üs alma üzerine kurulu olan bahsettiğiniz nokta. Bunun için büyük bir siparişin olduğunu anlayın$r$ st $g^r \equiv_p 1$ her bir görüntüyü hesaplamanız gerektiğinden, permütasyonlar için oldukça pratik olmadığından memnun $g^i$ a kadar $g^r$, setinizin uzunluğu ile sınırlıdır $S$ hangi değiştirilecek.