पैरामीट्रीज्ड परमीशन फंक्शन
मैं एक समारोह बनाने के लिए रास्ता खोज रहा हूँ जो निम्न चित्र में दर्शाए गए तरीके से काम करेगा:
यही कारण है, मैं इसे देखना चाहते दूसरे स्थान पर रखना एक दिया सरणी में तत्वों में से कुछ में उन्हें डाल करने के लिए अलग अलग क्रम एक के आधार पर पैरामीटर मैं इसे देने के लिए, ताकि मूल सेट (उन मैं धूसर पृष्ठभूमि के साथ चिह्नित) से अपनी पसंद के नंबर सब होगा आउटपुट सरणी (मोटी रेखा के बाईं ओर) की शुरुआत में एक निरंतर सीमा के रूप में समाप्त होता है, जबकि अन्य सभी तत्व (लाल पृष्ठभूमि) उस सरणी में शेष पदों पर (मोटी रेखा के दाईं ओर) समाप्त होते हैं ।
प्रत्येक आउटपुट रेंज (ग्रे या लाल) में उन तत्वों का क्रम मेरे लिए कोई मायने नहीं रखता है। उन्हें उस फ़ंक्शन द्वारा किसी भी मनमानी क्रम में रखा जा सकता है, जो चयनित इनपुट तत्वों (ग्रे) की एक विशेष पसंद के लिए गणना करने के लिए सरल है। केवल एक चीज जो मायने रखती है वह यह है कि वे सभी चयनित तत्व (ग्रे) सीमा के एक तरफ समाप्त होते हैं, जबकि अन्य तत्व (लाल) उस सीमा के दूसरी तरफ समाप्त होते हैं, और दो रेंज निरंतर होते हैं।
इस फ़ंक्शन को पैरामीट्रिजेबल होने की आवश्यकता है ताकि इस सरणी के सभी संभावित क्रमपरिवर्तन में से, मैं उस विशेष क्रमचय को चुन सकूं, जो फ़ंक्शन के सूत्र में कुछ संख्यात्मक पैरामीटर (या मापदंडों) को निर्दिष्ट करके तत्वों को उस विशेष क्रम में रखता है।
एक संख्यात्मक पैरामीटर बेहतर होता है, क्योंकि केवल एक क्रमपरिवर्तन होता है जो सभी तत्वों को इस विशेष क्रम में रखता है, और यह संख्या उस क्रमांकन की "पहचान संख्या" हो सकती है, लेकिन अगर यह प्राप्त करना कठिन होगा, तो कई संख्यात्मक पैरामीटर स्वीकार्य हैं , जब तक कि यह चुने हुए तत्वों की संख्या से अधिक नहीं है (जो शायद इसे वैसे भी प्रयास के लायक नहीं बनाएगा)।
क्या इनपुट सरणी से "चुने हुए तत्वों" का सबसेट दिया गया है, इस तरह के फ़ंक्शन के लिए एक व्यवस्थित तरीके से सूत्र बनाने का एक तरीका है? शायद मॉड्यूलर अंकगणित या परिमित क्षेत्रों के आधार पर कुछ? एक त्वरित वेब खोज ने मुझे "क्रमपरिवर्तन बहुपद" नामक एक शब्द दिया, जो पहली नज़र में इस समस्या से किसी भी तरह से संबंधित प्रतीत होता है, लेकिन मुझे उनके बारे में सभी संसाधन मिल सकते हैं कुछ मोटे गणित हैं जो उस क्षेत्र में बहुत अधिक पृष्ठभूमि की आवश्यकता होती है यह समझने के लिए कि क्या चल रहा है (मैं सिर्फ एक आईटी इंजीनियर / प्रोग्रामर हूं जो कुछ प्रोग्रामिंग समस्या का समाधान ढूंढ रहा है, पेशेवर गणितज्ञ नहीं: 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$तत्व। यह परिणाम है कि Linearised Permutation Polynomials के समूह पर$F_{q^n}$ रचना के तहत और उल्टे Matrices के समूह पर $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)))$$
कंप्यूटर विज्ञान के संदर्भ में, आपको Linearised Permutation Polynomials की गणना करने की आवश्यकता नहीं है, इसके बजाय, आप एक प्राइम फील्ड पर इनवर्टेड स्क्वायर मैट्रिसेस या ऐसे फील्ड के एक्सटेंशन फील्ड के साथ काम कर सकते हैं। क्यों? खैर, यह साबित हो गया है कि Linearised Permutation Polynomials over$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$वें क्रमपरिवर्तन एक और बिंदु, वह है जिसका आपने उल्लेख किया है, जो मॉड्यूलर घातांक पर आधारित है। उसके लिए, यह समझें कि एक बड़ा आदेश है$r$ अनुसूचित जनजाति $g^r \equiv_p 1$ यह संतुष्ट है कि यह क्रमपरिवर्तन के लिए काफी अव्यावहारिक है, क्योंकि आपको प्रत्येक छवि की गणना करनी चाहिए $g^i$ जब तक $g^r$, जो आपके सेट की लंबाई से घिरा है $S$ जिसे अनुमति दी जा रही है।