लेहमर कोड

गणित में और विशेष रूप से साहचर्य में, लेहमर कोड n संख्याओं के अनुक्रम के प्रत्येक संभावित क्रमचय को कूटबद्ध करने का एक विशेष तरीका है। यह क्रमचय क्रम परिवर्तन के लिए एक योजना का एक उदाहरण है और एक व्युत्क्रम (असतत गणित) तालिका का एक उदाहरण है।

लेहमर कोड का नाम डेरिक हेनरी लेहमर के संदर्भ में रखा गया है, लेकिन कोड कम से कम 1888 से जाना जाता था।

कोड

लेहमर कोड इस तथ्य का उपयोग करता है कि वहाँ हैं

$n!=n\times (n-1)\times \cdots \times 2\times 1$

एन संख्याओं के अनुक्रम के क्रमपरिवर्तन। यदि एक क्रमचय σ अनुक्रम के माध्यम से निर्दिष्ट किया जाता है (σ₁, ..., पी_n) इसकी 1, …, n की छवियों का, तो यह n संख्याओं के अनुक्रम के माध्यम से एन्कोड किया गया है, लेकिन ऐसे सभी क्रम मान्य नहीं हैं क्योंकि प्रत्येक संख्या का एकमात्र एक बार उपयोग किया जाना चाहिए। इसके विपरीत यहां पर विचार किए गए एनकोडिंग n मानों के एक सेट से पहली संख्या चुनते हैं, अगले नंबर के एक निश्चित सेट से n − 1 मान, और इसी प्रकार अंतिम संख्या तक संभावनाओं की संख्या घटाना जिसके लिए एकमात्र एक निश्चित मान की अनुमति है; इन सेटों से चुनी गई संख्याओं का प्रत्येक क्रम एक एकल क्रमचय को कूटबद्ध करता है। चूँकि कई एनकोडिंग को परिभाषित किया जा सकता है, लेहमर कोड में कई अतिरिक्त उपयोगी गुण हैं; यह क्रम है

$L(\sigma )=(L(\sigma )_{1},\ldots ,L(\sigma )_{n})\quad {\text{where}}\quad L(\sigma )_{i}=\#\{j>i:\sigma _{j}<\sigma _{i}\},$

दूसरे शब्दों में शब्द L(σ)_i शब्दों की संख्या (σ) में गिनता है₁, ..., पी_n) σ के दाईं ओर_i जो इससे छोटे हैं, 0 और के बीच की संख्या n − i, के लिए अनुमति n + 1 − i विभिन्न मान।

सूचकांकों की एक जोड़ी (i,j) के साथ i < j और σ_i > σ_j को σ, और L(σ) का उलटा कहा जाता है_i व्युत्क्रमों की संख्या (i, j) की गणना करता है i निश्चित और भिन्न j के साथ। यह इस प्रकार है कि L(σ)₁ + L(σ)₂ + … + L(σ)_n σ के व्युत्क्रमों की कुल संख्या है, जो क्रमचय को पहचान क्रमपरिवर्तन में बदलने के लिए आवश्यक आसन्न परिवर्तनों की संख्या भी है। लेहमर कोड के अन्य गुणों में सम्मलित है कि दो क्रमपरिवर्तनों के कूटलेखन का शब्दकोषीय क्रम उनके अनुक्रमों (σ) के समान है₁, ..., पी_n), कि कोड में कोई भी मान 0 क्रमचय में दाएँ-से-बाएँ न्यूनतम प्रतिनिधित्व करता है (अर्थात, एक σ_i किसी से छोटा σ_j इसके दाईं ओर), और एक मान n − i

स्थिति पर मैं समान रूप से दाएं-से-बाएं अधिकतम को दर्शाता है, और यह कि σ का लेहमर कोड लेक्सिकोग्राफिक क्रम में n के क्रमपरिवर्तन की सूची में अपनी स्थिति के भाज्य संख्या प्रणाली प्रतिनिधित्व के साथ मेल खाता है (0 से प्रारंभ होने वाले पदों की संख्या)।

निश्चित छोटे मान के साथ व्युत्क्रमों की गणना करके, निश्चित i के अतिरिक्त निश्चित j के लिए व्युत्क्रम (i, j) की गणना करके इस एन्कोडिंग के बदलाव प्राप्त किए जा सकते हैं। σ_j छोटे इंडेक्स i के अतिरिक्त, या व्युत्क्रम के अतिरिक्त गैर-इनवर्जन की गणना करके; चूँकि यह मौलिक रूप से अलग प्रकार के एन्कोडिंग का उत्पादन नहीं करता है, एन्कोडिंग के कुछ गुण तदनुसार बदल जाएंगे। विशेष रूप से एक निश्चित छोटे मूल्य के साथ उलटा गिनती σ_j σ की व्युत्क्रम तालिका देता है, जिसे व्युत्क्रम क्रमचय के लेहमर कोड के रूप में देखा जा सकता है।

एन्कोडिंग और डिकोडिंग

यह सिद्ध करने का सामान्य तरीका है कि n! n वस्तुओं के विभिन्न क्रमपरिवर्तनों का निरीक्षण करना है कि पहली वस्तु को चुना जा सकता है n अलग-अलग विधियां, अगली वस्तु अंदर n − 1 अलग-अलग तरीकों से (क्योंकि पहली वाली संख्या को चुनना वर्जित है), अगले में n − 2 अलग-अलग विधियां (क्योंकि अब 2 वर्जित मान हैं), और इसी प्रकार। पसंद की इस स्वतंत्रता का प्रत्येक चरण में एक संख्या में अनुवाद करने पर, एक कोडिंग एल्गोरिथम प्राप्त होता है, एक वह जो दिए गए क्रमचय के लेहमर कोड को खोजता है। किसी को वस्तुओं को संख्याओं के रूप में मानने की आवश्यकता नहीं है, लेकिन वस्तुओं के सेट के कुल क्रम की आवश्यकता है। चूँकि कोड संख्याएँ 0 से प्रारंभ होनी हैं, प्रत्येक वस्तु σ को एनकोड करने के लिए उपयुक्त संख्या_i के माध्यम से उन वस्तुओं की संख्या है जो उस बिंदु पर उपलब्ध थीं (इसलिए वे स्थिति i से पहले नहीं होती हैं), लेकिन जो वस्तु σ से छोटी हैं_i वास्तव में चुना गया। (अनिवार्य रूप से ऐसी वस्तुओं को किसी स्थान पर प्रकट होना चाहिए j > i, और (i,j) एक उलटा होगा, जो दर्शाता है कि यह संख्या वास्तव में L(σ) है_i.)

प्रत्येक वस्तु को एनकोड करने के लिए यह संख्या कई तरीकों से प्रत्यक्ष गणना के माध्यम से पाई जा सकती है (प्रत्यक्ष रूप से व्युत्क्रमों की गिनती, या किसी दिए गए से छोटी वस्तुओं की कुल संख्या को सही करना, जो कि सेट में 0 से प्रारंभ होने वाली इसकी अनुक्रम संख्या है, जो हैं अपनी स्थिति में अनुपलब्ध)। एक और तरीका जो जगह में है, लेकिन वास्तव में अधिक कुशल नहीं है, {0, 1, ... के क्रमचय के साथ प्रारंभ करना है। n − 1} प्रत्येक वस्तु को उसकी उल्लिखित अनुक्रम संख्या के माध्यम से प्रदर्शित करके प्राप्त किया जाता है, और फिर प्रत्येक प्रविष्टि x के लिए, बाएं से दाएं के क्रम में, x से बड़ी सभी प्रविष्टियों (अभी भी) में से 1 घटाकर (तथ्य को दर्शाने के लिए) वस्तुओं को उसके दाईं ओर सही करें x से संबंधित वस्तु अब उपलब्ध नहीं है)। अक्षरों के क्रमचय B,F,A,G,D,E,C के लिए विशेष रूप से एक लेहमर कोड, वर्णानुक्रम में क्रमबद्ध, पहले अनुक्रम संख्या 1,5,0,6,3,4,2 की सूची देगा, जो है क्रमिक रूप से परिवर्तित होता है।

${\begin{matrix}\mathbf {1} &5&0&6&3&4&2\\1&\mathbf {4} &0&5&2&3&1\\1&4&\mathbf {0} &4&2&3&1\\1&4&0&\mathbf {3} &1&2&0\\1&4&0&3&\mathbf {1} &2&0\\1&4&0&3&1&\mathbf {1} &0\\1&4&0&3&1&1&\mathbf {0} \\\end{matrix}}$

जहां अंतिम पंक्ति लेहमर कोड है (अगली पंक्ति बनाने के लिए बोल्डफेस तत्व के दाईं ओर बड़ी प्रविष्टियों से प्रत्येक पंक्ति में 1 घटाया जाता है)।

किसी दिए गए सेट के क्रमचय में एक लेहमर कोड को डिकोड करने के लिए, बाद की प्रक्रिया को उलटा किया जा सकता है: प्रत्येक प्रविष्टि x के लिए, दाएं से बाएं क्रम में, उन सभी (वर्तमान में) से अधिक 1 जोड़कर आइटम को उसके दाईं ओर सही करें या एक्स के बराबर; अंत में {0, 1, ... के परिणामी क्रमचय की व्याख्या करें n − 1} अनुक्रम संख्या के रूप में (यदि {1, 2, … n} का क्रमपरिवर्तन मांगा जाता है तो प्रत्येक प्रविष्टि में 1 जोड़ने के बराबर है)। वैकल्पिक रूप से लेहमर कोड की प्रविष्टियों को बाएँ से दाएँ संसाधित किया जा सकता है, और एक संख्या के रूप में व्याख्या की जा सकती है जो ऊपर बताए गए तत्व की अगली पसंद का निर्धारण करती है; इसके लिए उपलब्ध तत्वों की एक सूची बनाए रखने की आवश्यकता होती है, जिसमें से प्रत्येक चयनित तत्व को हटा दिया जाता है। उदाहरण में इसका अर्थ होगा {A,B,C,D,E,F,G} (जो कि B है) से तत्व 1 को चुनना, फिर {A,C,D,E,F,G} से तत्व 4 को चुनना (जो है एफ), फिर {A, C, D, E, G} से तत्व 0 (ए दे रहा है) और इसी प्रकार, अनुक्रम B, F, A, G, D, E, C का पुनर्निर्माण।

कॉम्बिनेटरिक्स और संभावनाओं के लिए आवेदन

रिश्तेदार रैंकों की स्वतंत्रता

लेहमर कोड सममित समूह S से एक आक्षेप को परिभाषित करता है_n कार्टेशियन उत्पाद के लिए $[n]\times [n-1]\times \cdots \times [2]\times [1]$, जहां [के] के-तत्व सेट को निर्दिष्ट करता है $\{0,1,\ldots ,k-1\}$. परिणामस्वरूप, एस पर समान वितरण (असतत) के तहत_n, घटक एल (σ)_i एक समान रूप से वितरित यादृच्छिक चर को परिभाषित करता है [n − i], और ये यादृच्छिक चर पारस्परिक रूप से स्वतंत्रता (संभाव्यता सिद्धांत) हैं, क्योंकि वे कार्टेशियन उत्पाद के विभिन्न कारकों पर अनुमान हैं।

दाएं-से-बाएं मिनिमा और मैक्सिमा

परिभाषा : एक क्रम में यू=(में_k)_1≤k≤n, रैंक k पर 'राइट-टू-लेफ्ट मिनिमम' (resp. 'मैक्सिमम') होता है, अगर यू_kप्रत्येक तत्व यू की तुलना में सख्ती से छोटा (उत्तर सख्ती से बड़ा) है_ii>k के साथ, अर्थात इसके दाईं ओर।

चलो B(k) (जवाब H(k)) रैंक k पर दाएं-से-बाएं न्यूनतम (प्रतिक्रिया अधिकतम) होने की घटना है, अर्थात B(k) क्रमपरिवर्तन का सेट है $\scriptstyle \ {\mathfrak {S}}_{n}$ जो रैंक k पर दाएँ-से-बाएँ न्यूनतम (प्रतिक्रिया अधिकतम) प्रदर्शित करता है। हमारे पास स्पष्ट रूप से है

<डिव वर्ग = केंद्र>$\{\omega \in B(k)\}\Leftrightarrow \{L(k,\omega )=0\}\quad {\text{and}}\quad \{\omega \in H(k)\}\Leftrightarrow \{L(k,\omega )=k-1\}.$

इस प्रकार संख्या एन_b(ओ) (उत्तर एन_hक्रमचय ω के लिए दाएं-से-बाएं न्यूनतम (प्रतिक्रिया अधिकतम) के (ω)) को 1/k के संबंधित पैरामीटर के साथ प्रत्येक स्वतंत्र बर्नौली यादृच्छिक चर के योग के रूप में लिखा जा सकता है:

<डिव वर्ग = केंद्र>$N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{B(k)}\quad {\text{and}}\quad N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{H(k)}.$

दरअसल, जैसा कि एल (के) समान नियम का पालन करता है $\scriptstyle \ [\![1,k]\!],$ <डिव वर्ग = केंद्र>$\mathbb {P} (B(k))=\mathbb {P} (L(k)=0)=\mathbb {P} (H(k))=\mathbb {P} (L(k)=k-1)={\tfrac {1}{k}}.$

बरनौली यादृच्छिक चर के लिए जनक फलन $1\!\!1_{B(k)}$ है

<डिव वर्ग = केंद्र>$G_{k}(s)={\frac {k-1+s}{k}},$

इसलिए N का जनरेटिंग फंक्शन_bहै

<डिव वर्ग = केंद्र>$G(s)=\prod _{k=1}^{n}G_{k}(s)\ =\ {\frac {s^{\overline {n}}}{n!}}$

(गिरते और बढ़ते फैक्टोरियल नोटेशन का उपयोग करके),

जो हमें उत्पादन समारोह के लिए उत्पाद सूत्र को पुनर्प्राप्त करने की अनुमति देता है

पहली प्रकार की स्टर्लिंग संख्या (अहस्ताक्षरित)।

सचिव समस्या

Main article: सचिव समस्या

यह एक इष्टतम रोक समस्या है, निर्णय सिद्धांत, सांख्यिकी और अनुप्रयुक्त संभावनाओं में एक क्लासिक है, जहां एक यादृच्छिक क्रमचय धीरे-धीरे इसके लेहमर कोड के पहले तत्वों के माध्यम से प्रकट होता है, और जहां लक्ष्य ठीक तत्व k पर रुकना है जैसे कि σ( k)=n, चूँकि एकमात्र उपलब्ध जानकारी (लेहमर कोड का k प्रथम मान) σ(k) की गणना करने के लिए पर्याप्त नहीं है।

कम गणितीय शब्दों में: n आवेदकों की एक श्रृंखला का एक के बाद एक साक्षात्कार किया जाता है। साक्षात्कारकर्ता को सर्वश्रेष्ठ आवेदक को किराए पर लेना चाहिए, लेकिन अपना निर्णय ("किराया" या "किराया नहीं"), अगले आवेदक का साक्षात्कार किए बिना (और सभी आवेदकों का साक्षात्कार किए बिना एक फोर्टियोरी) लेना चाहिए।

साक्षात्कारकर्ता इस प्रकार k की रैंक जानता है वें आवेदक, इसलिए, अपने k बनाने के समय वें निर्णय, साक्षात्कारकर्ता लेहमर कोड के एकमात्र k पहले तत्वों को जानता है, चूँकि उसे एक अच्छी प्रकार से सूचित निर्णय लेने के लिए उन सभी को जानने की आवश्यकता होगी।

इष्टतम रणनीतियों का निर्धारण करने के लिए (अर्थात जीत की संभावना को अधिकतम करने वाली रणनीति), लेहमर कोड के सांख्यिकीय गुण महत्वपूर्ण हैं।

कथित तौर पर, जोहान्स केप्लर ने स्पष्ट रूप से इस सचिव की समस्या को अपने एक दोस्त को उस समय उजागर किया जब वह अपना मन बनाने की प्रयास कर रहा था और अपनी दूसरी पत्नी के रूप में ग्यारह भावी दुल्हनों में से एक को चुनने की प्रयास कर रहा था। उनकी पहली शादी एक नाखुश थी, खुद से परामर्श किए बिना तय की गई थी, और इस प्रकार वह बहुत चिंतित थे कि वे सही निर्णय पर पहुंच सकें सकते हैं।

समान अवधारणाएँ

दो एक जैसे वेक्टर उपयोग में होते हैं। उनमें से एक को अक्सर उलटा वेक्टर कहा जाता है, जैसे वोल्फरम अल्फा द्वारा। इनवर्शन (विविध गणित) § इनवर्शन संबंधित वेक्टर देखें।

ग्रन्थसूची

• Mantaci, Roberto; Rakotondrajao, Fanja (2001), "A permutation representation that knows what "Eulerian" means", Discrete Mathematics and Theoretical Computer Science (4): 101–108, archived from the original on 2004-11-16
• Knuth, Don (1981), The art of computer programming, vol. 3, Reading: Addison-Wesley, pp. 12–13