लेक्सिकोग्राफिक ऑर्डर: Difference between revisions

Revision as of 15:58, 30 March 2023

गणित में, लेक्सिकोग्राफ़िक या लेक्सिकोोग्राफ़िकल ऑर्डर (जिसे शब्दकोश: के वर्णमाला आदेश के रूप में भी जाना जाता है) व्यवस्थित चिह्नों की अनुक्रमिक अनुक्रम या एक पूर्ण आदेश सेट के तत्वों के लिए शब्दकोशों के वर्णमाला क्रम आदेश का एक सामान्यीकरण है।

लेक्सिकोोग्राफिक ऑर्डरिंग के कई रूप वेरिएंट और सामान्यीकरण हैं। एक वेरिएंट विभिन्न लंबाई के अनुक्रमों के लिए लागू होता है, जहां उनके तत्वों को ध्यान में लेने से पहले अनुक्रमों की लंबाई की तुलना की जाती है।

साहचर्य में व्यापक रूप से उपयोग किया जाने वाला एक अन्य संस्करण, परिमित सेट को कुल क्रम निर्दिष्ट करके और उपसमुच्चय को अनुक्रम बढ़ते और घटते में परिवर्तित करके दिए गए परिमित सेट के सबसेट का आदेश देता है, जिसके लिए लेक्सिकोोग्राफ़िकल ऑर्डर लागू होता है।

एक सामान्यीकृती पूंजीत आदेशित सेटों के कार्टेशियन उत्पाद पर एक आदेश परिभाषित करती है; यह आदेश एक पूर्ण आदेश होता है यदि और केवल यदि कार्टेशियन उत्पाद के सभी अंश पूर्ण रूप से आदेशित होते हैं।

प्रेरणा और परिभाषा

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

इस संरचना का आरंभ एक सीमित सेट $A$ ,के साथ होता है, जिसे अक्सर वर्णमाला कहा जाता है, जो पूर्ण आदेशित होता है। अर्थात्, $A$ में दो सिंबल $a$ और $b$ जो कि एक जैसे नहीं होते हैं, के लिए या तो $a < b$ होता है या फिर $b < a$ होता है।

$A$ के शब्द,शब्द $A$ के सिंबलों से बने सिंक्रोनस तार के समान निर्धारित होते हैं, जिनमें एक सिंबल के लिए लंबाई 1 का शब्द, दो सिंबलों के लिए लंबाई 2 का शब्द और इस तरह से आगे बढ़ते हैं, शून्य सिंदूर समेत सभी सीमित संख्याओं के शब्दों को भी शामिल करते हुए। इन सभी सीमित शब्दों के सेट पर लेक्सिकोग्राफिक आदेश शब्दों को

एक ही लंबाई के दो अलग-अलग शब्दों को देखते हुए कहें $a = a 1 a 2 ... a k$ और $b = b 1 b 2 ... b k$ , दो शब्दों का क्रम पहले स्थान पर प्रतीकों के वर्णमाला क्रम पर निर्भर करता है $i$ जहां दो शब्द भिन्न होते हैं (शब्दों की प्रारंभ से गिनती): $a < b$ यदि और एकमात्र यदि $a i < b i$ वर्णमाला के अंतर्निहित क्रम में $A$ .
यदि दो शब्दों की लम्बाई अलग-अलग है, तो सामान्यतया लेक्सिकोग्राफिकल आदेश छोटे शब्द को "ब्लैंक" (एक विशेष प्रतीक जो $A$ के हर तत्व से छोटा माना जाता है) से भर देता है जिससे कि शब्दों की लम्बाई समान हो जाती है, फिर शब्दों की तुलना पिछले मामले की तरह की जाती है।

कॉम्बिनेटरिक्स में, दूसरे स्थितियों के लिए अधिकांशतः एक और सम्मेलन का उपयोग किया जाता है, जिससे एक छोटा अनुक्रम हमेशा एक लंबे अनुक्रम से छोटा होता है। लेक्सिकोोग्राफिक ऑर्डर के इस प्रकार को कभी-कभी कहा जाता है शॉर्टलेक्स ऑर्डर.

शब्दावली क्रम में, थॉमस शब्द थॉम्पसन से पहले प्रकट होता है क्योंकि वे पहले पांचवें अक्षर ('ए' और 'पी') में भिन्न होते हैं, और अक्षर 'ए' वर्णमाला में 'पी' अक्षर से पहले आता है। क्योंकि यह पहला अंतर है, इस स्थितियों में 5वां अक्षर वर्णमाला क्रम के लिए सबसे महत्वपूर्ण अंतर है।

लेक्सिकोग्राफिकल ऑर्डर की एक महत्वपूर्ण संपत्ति यह है कि प्रत्येक के लिए $n$ , लंबाई के शब्दों का सेट $n$ शब्दकोषीय क्रम के माध्यम से सुव्यवस्थित है (बशर्ते वर्णमाला परिमित हो); अर्थात लंबाई के शब्दों का हर घटता क्रम $n$ परिमित है (या समतुल्य रूप से, प्रत्येक गैर-खाली सबसेट में कम से कम तत्व होता है)।^[1]^[2] यह सच नहीं है कि सभी परिमित शब्दों का समुच्चय सुव्यवस्थित है; उदाहरण के लिए, शब्दों के अनंत समुच्चय {b, ab, aab, aaab, ...} का कोई शब्दकोषिक रूप से प्रारंभिक तत्व नहीं है।

अंक प्रणाली और दिनांक

शब्दकोषीय क्रम का प्रयोग न एकमात्र शब्दकोशों में किया जाता है, बल्कि सामान्यतः संख्याओं और तिथियों के लिए भी किया जाता है।

रोमन अंक प्रणाली की कमियों में से एक यह है कि यह हमेशा तुरंत स्पष्ट नहीं होता है कि दो संख्याओं में से कौन सी संख्या छोटी है। दूसरी ओर, हिंदू-अरबी अंक प्रणाली की स्थितीय संकेतन के साथ, संख्याओं की समानता करना आसान है, क्योंकि गैर-ऋणात्मक पूर्णांकों पर प्राकृतिक क्रम लेक्सिकोग्राफ़िक क्रम के वैरिएंट शॉर्टलेक्स ऑर्डर के समान है। वास्तव में, स्थितीय संकेतन के साथ, एक गैर-ऋणात्मक पूर्णांक को संख्यात्मक अंकों के अनुक्रम के माध्यम से दर्शाया जाता है, और एक पूर्णांक दूसरे से बड़ा होता है यदि या तो इसमें अधिक अंक होते हैं (अग्रणी शून्य को अनदेखा करते हुए) या अंकों की संख्या समान होती है और पहले ( सबसे महत्वपूर्ण) अंक जो भिन्न होता है वह बड़ा होता है।

दशमलव संकेतन में लिखी गई वास्तविक संख्याओं के लिए, शब्दकोषीय क्रम का थोड़ा भिन्न संस्करण उपयोग किया जाता है: दशमलव बिंदु के बाईं ओर के भागों की समानता पहले की प्रकार की जाती है; यदि वे समान हैं, तो दशमलव बिंदु के दायीं ओर के भागों की समानता शब्दकोषीय क्रम से की जाती है। इस संदर्भ में पैडिंग 'रिक्त' 0 अंकों के पीछे है।

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

लेक्सिकोग्राफिक ऑर्डरिंग के गैर-शब्दकोश उपयोग का एक और उदाहरण आईएसओ 8601 मानक में तारीखों के लिए प्रकट होता है, जो YYYY-MM-DD के रूप में एक तारीख को व्यक्त करता है। इस स्वरूपण योजना का यह लाभ है कि वर्णों के अनुक्रमों पर लेक्सिकोग्राफ़िकल क्रम, जो तारीखों का प्रतिनिधित्व करते हैं, कालानुक्रमिक क्रम के साथ मेल खाता है: पहले की सीई तिथि 9999 वर्ष तक की बाद की तारीख की समानता में लेक्सिकोग्राफ़िकल क्रम में छोटी होती है। एक अलग छँटाई एल्गोरिथ्म की आवश्यकता से बचना आसान है।

== शब्दों का मोनोइड == मोनोइड ऑफ वर्ड्स} डी.एस एक वर्णमाला पर $A$ मुक्त मोनोइड ओवर है $A$ . अर्थात्, मोनॉइड के तत्व तत्वों के परिमित अनुक्रम (शब्द) हैं $A$ (लंबाई 0 के खाली अनुक्रम सहित), और संक्रिया (गुणा) शब्दों का संयोजन है। शब्द $u$ दूसरे शब्द का उपसर्ग (कंप्यूटर विज्ञान) (या 'ट्रंकेशन') है $v$ यदि कोई शब्द सम्मलित है $w$ ऐसा है कि $v = uw$ . इस परिभाषा से, खाली शब्द ( $\varepsilon$ ) प्रत्येक शब्द का एक उपसर्ग है, और प्रत्येक शब्द स्वयं का एक उपसर्ग है (के साथ $w$ $=\varepsilon$ ); यदि इन स्थितियों को बाहर रखा जाना है तो सावधानी बरतनी चाहिए।

इस शब्दावली के साथ, शब्दावली क्रम की उपरोक्त परिभाषा अधिक संक्षिप्त हो जाती है: आंशिक आदेश या कुल आदेश सेट को देखते हुए $A$ , और दो शब्द $a$ और $b$ ऊपर $A$ ऐसा है कि $b$ खाली नहीं है, तो किसी के पास है $a < b$ शब्दकोषीय क्रम के अनुसार , यदि निम्न में से कम से कम एक स्थिति संतुष्ट होती है:

$a$ का उपसर्ग है $b$
शब्द सम्मलित हैं $u$ , $v$ , $w$ (संभवतः खाली) और एलिमेंट्स $x$ और $y$ का $A$ ऐसा है कि

x < y

a = uxv

b = uyw

ध्यान दें कि, इस परिभाषा में उपसर्ग स्थिति के कारण, $\varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,$ कहाँ $\varepsilon$ खाली शब्द है।

यदि $\,<\,$ पर कुल आदेश है $A,$ तो शब्दों पर शब्दकोष क्रम है $A.$ चूंकि, सामान्यतः यह एक अच्छा क्रम नहीं है, के होने पर भी वर्णमाला हो $A$ सुव्यवस्थित है। उदाहरण के लिए, यदि $A = {a, b}$ , औपचारिक भाषा ${a n b | n \geq 0, b > ε}$ कोश के क्रम में कोई कम से कम तत्व नहीं है: $... < aab < ab < b$ .

चूंकि कई अनुप्रयोगों के लिए अच्छी प्रकार से ऑर्डर की आवश्यकता होती है, लेक्सिकोोग्राफिक ऑर्डर का एक प्रकार अधिकांशतः उपयोग किया जाता है। यह अच्छी व्यवस्था, जिसे कभी-कभी कहा जाता है शॉर्टलेक्स या अर्ध-शब्दकोशीय क्रम, पहले शब्दों की लंबाई पर विचार करना सम्मलित है (यदि $length(a) < length(b)$ , तब $a<b$ ), और, यदि लंबाई समान हैं, तो शब्दकोषीय क्रम का उपयोग करते हुए। यदि आदेश चालू है $A$ एक वेल-ऑर्डर है, शॉर्टलेक्स ऑर्डर के लिए भी यही सच है।^[2]^[3]

कार्टेशियन उत्पाद

लेक्सिकोोग्राफ़िकल ऑर्डर ऑर्डर किए गए सेट के कार्टेशियन उत्पाद पर ऑर्डर को परिभाषित करता है, जो कुल ऑर्डर होता है जब ये सभी सेट पूरी प्रकार से ऑर्डर किए जाते हैं। कार्टेशियन उत्पाद का तत्व $E_{1}\times \cdots \times E_{n}$ एक क्रम है जिसका $i$ ^वें तत्व का है $E_{i}$ हर एक के लिए $i.$ अनुक्रमों के लेक्सिकोोग्राफ़िकल ऑर्डर का मूल्यांकन एकमात्र उन तत्वों की समानता करता है जिनके अनुक्रमों में समान रैंक है, लेक्सिकोोग्राफ़िकल ऑर्डर ऑर्डर किए गए सेटों के कार्टेशियन उत्पादों तक फैला हुआ है।

विशेष रूप से, दो आंशिक रूप से आदेशित सेट दिए गए हैं $A$ और $B,$ कार्टेशियन उत्पाद पर लेक्सिकोोग्राफिक ऑर्डर $A\times B$ परिभाषित किया जाता है

(a,b)\leq \left(a^{\prime },b^{\prime }\right){\text{ if and only if }}a<a^{\prime }{\text{ or }}\left(a=a^{\prime }{\text{ and }}b\leq b^{\prime }\right),

परिणामआंशिक क्रम है। यदि

A

और

B

प्रत्येक कुल आदेश हैं, तो परिणाम कुल आदेश भी होता है। इस प्रकार दो पूरी प्रकार से आदेशित सेटों का शब्दकोषीय क्रम उनके उत्पाद क्रम का रैखिक विस्तार है।

ऑर्डर किए गए सेटों के अनंत परिवार के कार्टेशियन उत्पाद पर समान रूप से लेक्सिकोग्राफिक ऑर्डर को परिभाषित किया जा सकता है, यदि परिवार को गैर-नकारात्मक पूर्णांकों के माध्यम से अनुक्रमित किया जाता है, या अधिक सामान्यतः सुव्यवस्थित सेट के माध्यम से । यदि प्रत्येक कारक सेट पूरी प्रकार से ऑर्डर किया गया है तो यह सामान्यीकृत लेक्सिकोोग्राफ़िकल ऑर्डर कुल ऑर्डर है।

परिमित स्थितियों के विपरीत, अच्छी प्रकार से ऑर्डर का अनंत उत्पाद लेक्सिकोग्राफ़िकल ऑर्डर के माध्यम से आवश्यक नहीं है। उदाहरण के लिए, अनगिनत अनंत द्विआधारी अनुक्रमों का सेट (परिभाषा के अनुसार, गैर-नकारात्मक पूर्णांक से कार्यों का सेट $\{0,1\},$ कैंटर स्पेस के रूप में भी जाना जाता है $\{0,1\}^{\omega }$ ) सुव्यवस्थित नहीं है; अनुक्रमों का उपसमुच्चय जिसमें ठीक है $1$ (वह है, ${ 100000..., 010000..., 001000..., ... }$ ) के माध्यम से प्रेरित शब्दकोष क्रम के अनुसार कम से कम तत्व नहीं है $0<1,$ क्योंकि $100000... > 010000... > 001000... > ...$ एक अनंत अवरोही श्रृंखला है।^[1] इसी प्रकार, अनंत लेक्सिकोग्राफिक उत्पाद नोथेरियन संबंध भी नहीं है क्योंकि $011111... < 101111... < 110111 ... < ...$ एक अनंत आरोही श्रृंखला है।

== एक सुव्यवस्थित सेट == पर कार्य करता है

एक सुव्यवस्थित सेट से कार्य करता है $X$ पूरी प्रकार से ऑर्डर किए गए सेट के लिए $Y$ के माध्यम से अनुक्रमित अनुक्रमों से पहचाना जा सकता है $X$ के तत्वों का $Y.$ इस प्रकार उन्हें लेक्सिकोोग्राफिक ऑर्डर और ऐसे दो कार्यों के लिए आदेश दिया जा सकता है $f$ और $g,$ शब्दकोषीय क्रम इस प्रकार सबसे छोटे के लिए उनके मूल्यों के माध्यम से निर्धारित किया जाता है $x$ ऐसा है कि $f(x)\neq g(x).$ यदि $Y$ भी सुव्यवस्थित है और $X$ परिमित है, तो परिणामी क्रम अच्छी-व्यवस्था है। जैसा कि ऊपर दिखाया गया है, यदि $X$ अनंत है ऐसा नहीं है।

परिमित सबसेट

के 3-उपसमुच्चयों का क्रम

\{1,\ldots ,6\},

लाल वर्गों के सेट के रूप में प्रतिनिधित्व, अनुक्रम (नीले रंग में), या उनके संकेतक कार्यों के माध्यम से , दशमलव संकेतन (ग्रे में) में परिवर्तित। ग्रे नंबर भी के सभी सबसेट में सबसेट की रैंक हैं

\{1,\ldots ,6\},

कोलेक्सिकोग्राफ़िकल ऑर्डर में गिने गए हैं, और 0 से प्रारंभ हो रहे हैं। लेक्सिकोग्राफ़िकल (लेक्स) और कोलेक्सिकोग्राफ़िकल (कोलेक्स) ऑर्डर सबसे ऊपर हैं और संबंधित रिवर्स ऑर्डर (रेव) नीचे हैं
एक ऑर्डर से उसके रिवर्स ऑर्डर तक जाता है, या तो ऊपर-नीचे के अतिरिक्त नीचे-ऊपर पढ़कर, या लाल और सफेद रंगों का आदान-प्रदान करके।

कॉम्बिनेटरिक्स में, किसी को अधिकांशतः गणना करनी होती है, और इसलिए किसी दिए गए सेट के परिमित सबसेट को ऑर्डर करना होता है $S.$ इसके लिए, सामान्यतः एक ऑर्डर चुनता है $S.$ फिर, सबसेट छँटाई $S$ इसे बढ़ते क्रम में बदलने के समान है। परिणामी अनुक्रमों पर लेक्सिकोग्राफ़िक क्रम इस प्रकार उपसमुच्चय पर आदेश उत्पन्न करता है, जिसे भी कहा जाता है लेक्सिकोग्राफिक ऑर्डर.

इस संदर्भ में, सामान्यतः पहले सबसेट को प्रमुखता के माध्यम से सॉर्ट करना पसंद करते हैं, जैसे शॉर्टलेक्स ऑर्डर में। इसलिए, निम्नलिखित में, हम निश्चित कार्डिनल के सबसेट पर एकमात्र आदेश पर विचार करेंगे।

उदाहरण के लिए, पूर्णांकों के प्राकृतिक क्रम का उपयोग करते हुए, तीन तत्वों के सबसेट पर लेक्सिकोोग्राफिक ऑर्डरिंग $S=\{1,2,3,4,5,6\}$ है

123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <

234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456

.

प्राकृतिक संख्याओं की दी गई कार्डिनैलिटी के परिमित उपसमुच्चयों को क्रमबद्ध करने के लिए, कोलेक्सिकोग्राफिक ऑर्डर (नीचे देखें) अधिकांशतः अधिक सुविधाजनक होता है, क्योंकि सभी प्रारंभिक खंड परिमित होते हैं, और इस प्रकार कोलेक्सिकोोग्राफिकल ऑर्डर प्राकृतिक संख्याओं और सेट के सेट के बीच आदेश समरूपता को परिभाषित करता है $n$ प्राकृतिक संख्या। लेक्सिकोग्राफिक ऑर्डर के लिए यह स्थिति नहीं है, जैसा कि लेक्सिकोोग्राफिक ऑर्डर के साथ, हमारे पास है, उदाहरण के लिए, $12n<134$ हर एक के लिए $n>2.$

जेड के समूह आदेश^एन

होने देना $\mathbb {Z} ^{n}$ रैंक का मुक्त एबेलियन समूह बनें $n,$ जिनके तत्व अनुक्रम हैं $n$ पूर्णांक, और संक्रिया योगात्मक समूह है। एक पूरी प्रकार से आदेशित समूह पर $\mathbb {Z} ^{n}$ कुल आदेश है, जो कि जोड़ के अनुकूल है, अर्थात

a<b\quad {\text{ if and only if }}\quad a+c<b+c.

लेक्सिकोोग्राफिक ऑर्डरिंग ग्रुप ऑर्डर है

\mathbb {Z} ^{n}.

लेक्सिकोोग्राफ़िकल ऑर्डरिंग का उपयोग सभी ग्रुप ऑर्डर को चिह्नित करने के लिए भी किया जा सकता है $\mathbb {Z} ^{n}.$ ^[4]^[5] वास्तव में, $n$ वास्तविक संख्या गुणांक वाले रेखीय रूप, मानचित्र को परिभाषित करते हैं $\mathbb {Z} ^{n}$ में $\mathbb {R} ^{n},$ जो कि अंतःक्षेपी है यदि रूप रैखिक रूप से स्वतंत्र हैं (यदि प्रपत्र आश्रित हैं तो यह अंतःक्षेपी भी हो सकता है, नीचे देखें)। इस मानचित्र की छवि पर लेक्सिकोोग्राफिक क्रम समूह क्रम को प्रेरित करता है $\mathbb {Z} ^{n}.$ रोबियानो की प्रमेय यह है कि प्रत्येक समूह आदेश इस प्रकार से प्राप्त किया जा सकता है।

अधिक त्रुटिहीन रूप से, एक समूह आदेश दिया गया $\mathbb {Z} ^{n},$ वहाँ एक पूर्णांक सम्मलित है $s\leq n$ और $s$ वास्तविक गुणांक वाले रेखीय रूप, जैसे कि प्रेरित मानचित्र $\varphi$ से $\mathbb {Z} ^{n}$ में $\mathbb {R} ^{s}$ निम्नलिखित गुण हैं;

$\varphi$ इंजेक्शन है;
परिणामी समरूपतावाद से $\mathbb {Z} ^{n}$ की छवि के लिए $\varphi$ ऑर्डर आइसोमोर्फिज्म है जब छवि को लेक्सिकोोग्राफिक ऑर्डर से लैस किया जाता है $\mathbb {R} ^{s}.$

शब्दकोश क्रम

5-चक्र (नीले रंग में)। कोलेक्स क्रम में क्रमपरिवर्तन का व्युत्क्रम (असतत गणित) (लाल रंग में) रेवकोलेक्स क्रम में है, और इसके विपरीत।

कोलेक्सिकोग्राफिक या कोलेक्स ऑर्डर लेक्सिकोोग्राफिक ऑर्डर का एक प्रकार है जो बाएं से दाएं को पढ़ने के अतिरिक्त दाएं से बाएं से परिमित अनुक्रमों को पढ़कर प्राप्त किया जाता है। अधिक त्रुटिहीन रूप से, चूँकि दो अनुक्रमों के बीच लेक्सिकोोग्राफ़िकल ऑर्डर के माध्यम से परिभाषित किया गया है

a 1 a 2 ... a k < lex b 1 b 2 ... b k

यदि

a i < b i

पहले के लिए

i

कहाँ

a i

और

b i

अलग होना,

कोलेक्सिकोग्राफिक ऑर्डर के माध्यम से परिभाषित किया गया है

a 1 a 2 ... a k < colex b 1 b 2 ... b k

यदि

a i < b i

आखिरी बार के लिये

i

कहाँ

a i

और

b i

अलग होना

सामान्यतः, कोलेक्सिकोग्राफ़िकल ऑर्डर और लेक्सिकोग्राफ़िकल ऑर्डर के बीच का अंतर बहुत महत्वपूर्ण नहीं है। चूंकि, बढ़ते अनुक्रमों पर विचार करते समय, सामान्यतः कोडिंग सबसेट के लिए, दो ऑर्डर महत्वपूर्ण रूप से भिन्न होते हैं।

उदाहरण के लिए, दो प्राकृतिक पूर्णांकों के बढ़ते अनुक्रमों (या सेटों) को व्यवस्थित करने के लिए, लेक्सिकोोग्राफ़िकल ऑर्डर प्रारंभ होता है

12 < 13 < 14 < 15 < ... < 23 < 24 < 25 < ... < 34 < 35 < ... < 45 < ...

,

और कोलेक्सिकोग्राफिक क्रम के माध्यम से प्रारंभ होता है

12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 < ...

.

किसी दी गई लंबाई के अनुक्रमों को बढ़ाने के लिए कोलेक्सिकोग्राफिक ऑर्डर की मुख्य संपत्ति यह है कि प्रत्येक प्रारंभिक खंड परिमित है। दूसरे शब्दों में, दी गई लंबाई के अनुक्रमों को बढ़ाने के लिए कोलेक्सिकोग्राफ़िकल ऑर्डर प्राकृतिक संख्याओं के साथ एक ऑर्डर समरूपता को प्रेरित करता है, और इन अनुक्रमों की गणना करने की अनुमति देता है। यह अधिकांशतः कॉम्बिनेटरिक्स में प्रयोग किया जाता है, उदाहरण के लिए क्रुस्कल-कटोना प्रमेय के प्रमाण में होता है।

एकपद

बहुपदों पर विचार करते समय, शर्तों का क्रम सामान्य रूप से कोई फर्क नहीं पड़ता, क्योंकि जोड़ क्रमविनिमेय है। चूंकि, कुछ कलन विधि, जैसे कि बहुपद लंबे विभाजन, को एक विशिष्ट क्रम में शब्दों की आवश्यकता होती है। बहुभिन्नरूपी बहुपदों के लिए कई मुख्य एल्गोरिदम ग्रोबनर आधारों से संबंधित हैं, अवधारणा जिसके लिए एक मोनोमियल ऑर्डर की पसंद की आवश्यकता होती है, जो कुल ऑर्डर है, जो एकपदीयों की मोनोइड संरचना के साथ संगत है। यहाँ संगत का अर्थ है $a<b{\text{ implies }}ac<bc,$ यदि मोनॉइड ऑपरेशन को गुणात्मक रूप से निरूपित किया जाता है। इस अनुकूलता का अर्थ है कि एक एकपदी के माध्यम से एक बहुपद का गुणनफल शब्दों के क्रम को नहीं बदलता है। ग्रोबनर आधारों के लिए, एक और शर्त पूरी होनी चाहिए, अर्थात् प्रत्येक गैर स्थिर मोनोमियल एकपदी से अधिक है $1$ . चूंकि अन्य संबंधित एल्गोरिदम के लिए इस स्थिति की आवश्यकता नहीं है, जैसे कि स्पर्शरेखा शंकु की गणना के लिए एल्गोरिदम बीजगणितीय ज्यामिति में परिभाषा।

जैसा कि ग्रोबनर आधार चर की एक निश्चित संख्या में बहुपदों के लिए परिभाषित किए गए हैं, एकपदी की पहचान करना आम है (उदाहरण के लिए $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ ) उनके प्रतिपादक वैक्टर के साथ (यहाँ $[1, 3, 0, 1, 2]$ ). यदि $n$ चरों की संख्या है, प्रत्येक मोनोमियल ऑर्डर इस प्रकार प्रतिबंध है $\mathbb {N} ^{n}$ के एक मोनोमियल ऑर्डर का $\mathbb {Z} ^{n}$ (ऊपर देखें § समूह के आदेश $\mathbb {Z} ^{n},$ वर्गीकरण के लिए)।

इन स्वीकार्य आदेशों में से एक लेक्सिकोग्राफिक ऑर्डर है। यह, ऐतिहासिक रूप से, सबसे पहले ग्रोबनेर ठिकानों को परिभाषित करने के लिए उपयोग किया गया है, और इसे कभी-कभी कहा जाता है pure lexicographical order इसे अन्य आदेशों से अलग करने के लिए जो कि एक शब्दावली क्रम से भी संबंधित होती है।

दूसरे में पहले कुल डिग्रियों की समानता करना और फिर लेक्सिकोोग्राफिक क्रम का उपयोग करके संघर्षों को हल करना सम्मलित है। इस आदेश का व्यापक रूप से उपयोग नहीं किया जाता है, क्योंकि या तो लेक्सिकोग्राफ़िकल ऑर्डर या डिग्री रिवर्स लेक्सिकोग्राफ़िकल ऑर्डर में सामान्यतः उत्तम गुण होते हैं। वह डिग्री रिवर्स लेक्सिकोग्राफिक ऑर्डर पहले कुल डिग्रियों की समानता करने में भी सम्मलित है, और कुल डिग्रियों की समानता के स्थितियों में, कोलेक्सिकोग्राफ़िक ऑर्डर के रिवर्स का उपयोग करते हुए। अर्थात्, दो घातांक सदिश दिए गए हैं, एक के पास

[a_{1},\ldots ,a_{n}]<[b_{1},\ldots ,b_{n}]

या तो

 $a_{1}+\cdots +a_{n}<b_{1}+\cdots +b_{n},$

या

a_{1}+\cdots +a_{n}=b_{1}+\cdots +b_{n}\quad {\text{ and }}\quad a_{i}>b_{i}{\text{ for the largest }}i{\text{ for which }}a_{i}\neq b_{i}.

इस आदेश के लिए, डिग्री एक के मोनोमियल्स का वही क्रम होता है जो संबंधित अनिश्चित होता है (यह स्थिति नहीं होगा यदि रिवर्स लेक्सिकोग्राफ़िकल ऑर्डर का उपयोग किया जाएगा)। एक ही कुल डिग्री के दो चरों में मोनोमियल्स की समानता करने के लिए, यह क्रम शब्दकोषीय क्रम के समान है। अधिक चरों के साथ ऐसा नहीं है। उदाहरण के लिए, तीन चर में दो डिग्री के मोनोमियल के एक्सपोनेंट वैक्टर के लिए, डिग्री रिवर्स लेक्सिकोग्राफिक ऑर्डर के लिए होता है:

[0,0,2]<[0,1,1]<[1,0,1]<[0,2,0]<[1,1,0]<[2,0,0]

लेक्सिकोोग्राफिक ऑर्डर के लिए, समान एक्सपोनेंट वैक्टर को ऑर्डर किया जाता है

[0,0,2]<[0,1,1]<[0,2,0]<[1,0,1]<[1,1,0]<[2,0,0].

डिग्री रिवर्स लेक्सिकोोग्राफ़िकल ऑर्डर की एक उपयोगी संपत्ति यह है कि एक सजातीय बहुपद कम से कम अनिश्चित का एक बहु है यदि और एकमात्र यदि इसके अग्रणी मोनोमियल (इसका बड़ा मोनोमियल) इस कम से कम अनिश्चित का एक बहु है।

यह भी देखें

मिलान
क्लीन-ब्रूवर ऑर्डर
लेक्सिकोग्राफिक प्राथमिकताएं - अर्थशास्त्र में लेक्सिकोग्राफिक ऑर्डर का एक अनुप्रयोग।
लेक्सिकोग्राफिक अनुकूलन - लेक्सिकोग्राफ़िकली-मैक्सिमम एलिमेंट खोजने की एल्गोरिथम समस्या।
यूनिट स्क्वायर पर लेक्सिकोग्राफिक ऑर्डर टोपोलॉजी
सार सूचकांक संकेतन ब्रेडिंग
लेक्सिकोग्राफिक रूप से न्यूनतम स्ट्रिंग रोटेशन
पढ़ने का क्रम
लंबी लाइन (टोपोलॉजी)
लिंडन शब्द
स्टार उत्पाद, आंशिक ऑर्डर के संयोजन का एक अलग प्रणाली
शॉर्टलेक्स ऑर्डर
कुल ऑर्डर पूरी प्रकार से ऑर्डर किए गए सेट के कार्टेशियन उत्पाद पर ऑर्डर

संदर्भ

↑ ^1.0 ^1.1 Egbert Harzheim (2006). ऑर्डर किए गए सेट. Springer. pp. 88–89. ISBN 978-0-387-24222-4.
↑ ^2.0 ^2.1 Franz Baader; Tobias Nipkow (1999). टर्म पुनर्लेखन और वह सब. Cambridge University Press. pp. 18–19. ISBN 978-0-521-77920-3.
↑ Calude, Cristian (1994). सूचना और यादृच्छिकता। एक एल्गोरिथम परिप्रेक्ष्य. EATCS Monographs on Theoretical Computer Science. Springer-Verlag. p. 1. ISBN 3-540-57456-5. Zbl 0922.68073.
↑ Robbiano, L. (1985). Term orderings on the polynomial ring. In European Conference on Computer Algebra (pp. 513-517). Springer Berlin Heidelberg.
↑ Weispfenning, Volker (May 1987), "Admissible Orders and Linear Forms", SIGSAM Bulletin, New York, NY, USA: ACM, 21 (2): 16–18, doi:10.1145/24554.24557, S2CID 10226875.

बाहरी संबंध

Learning materials related to Lexicographic and colexicographic order at Wikiversity

[Harzheim-1] 1.0 ^1.1 Egbert Harzheim (2006). ऑर्डर किए गए सेट. Springer. pp. 88–89. ISBN 978-0-387-24222-4.

[BaaderNipkow1999-2] 2.0 ^2.1 Franz Baader; Tobias Nipkow (1999). टर्म पुनर्लेखन और वह सब. Cambridge University Press. pp. 18–19. ISBN 978-0-521-77920-3.

[3] Calude, Cristian (1994). सूचना और यादृच्छिकता। एक एल्गोरिथम परिप्रेक्ष्य. EATCS Monographs on Theoretical Computer Science. Springer-Verlag. p. 1. ISBN 3-540-57456-5. Zbl 0922.68073.

[4] Robbiano, L. (1985). Term orderings on the polynomial ring. In European Conference on Computer Algebra (pp. 513-517). Springer Berlin Heidelberg.

[5] Weispfenning, Volker (May 1987), "Admissible Orders and Linear Forms", SIGSAM Bulletin, New York, NY, USA: ACM, 21 (2): 16–18, doi:10.1145/24554.24557, S2CID 10226875.

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
 {{short description|Generalization of the alphabetical order of dictionaries to sequences of elements of an ordered set}}
-{{more citations needed|date=January 2022}}
+{{Hatnote|गणित के बाहर समान रूप से नामित ऑर्डरिंग सिस्टम के लिए, [[वर्णानुक्रमिक क्रम]], [[प्राकृतिक क्रमबद्ध क्रम]], [[लेक्सिकोग्राफ़िक वरीयताएँ]], और [[कोलेशन]] देखें।}}
-{{Hatnote|For similarly named ordering systems outside mathematics, see [[alphabetical order]], [[natural sort order]], [[lexicographic preferences]], and [[collation]].}}
-गणित में, लेक्सिकोग्राफ़िक या लेक्सिकोोग्राफ़िकल ऑर्डर (जिसे लेक्सिकल ऑर्डर या [[शब्दकोश:]] ऑर्डर के रूप में भी जाना जाता है) ऑर्डर किए गए प्रतीकों के [[अनुक्रम]]ों या पूरी प्रकार से ऑर्डर किए गए सेट के तत्वों के अधिक सामान्य रूप से शब्दकोशों के [[वर्णमाला क्रम]] का सामान्यीकरण है।
+गणित में, लेक्सिकोग्राफ़िक या लेक्सिकोोग्राफ़िकल ऑर्डर (जिसे [[शब्दकोश:]] के वर्णमाला आदेश के रूप में भी जाना जाता है) व्यवस्थित चिह्नों की [[अनुक्रम|अनुक्रमिक]] अनुक्रम या एक पूर्ण आदेश सेट के तत्वों के लिए शब्दकोशों के [[वर्णमाला क्रम]] आदेश का एक सामान्यीकरण है।
-लेक्सिकोोग्राफिक ऑर्डरिंग के कई रूप और सामान्यीकरण हैं। एक संस्करण उनके तत्वों पर विचार करने से पहले अनुक्रमों की लंबाई की समानता  करके विभिन्न लंबाई के अनुक्रमों पर लागू होता है।
+लेक्सिकोोग्राफिक ऑर्डरिंग के कई रूप वेरिएंट और सामान्यीकरण हैं। एक वेरिएंट विभिन्न लंबाई के अनुक्रमों के लिए लागू होता है, जहां उनके तत्वों को ध्यान में लेने से पहले अनुक्रमों की लंबाई की तुलना की जाती है।
 [[साहचर्य]] में व्यापक रूप से उपयोग किया जाने वाला एक अन्य संस्करण, [[परिमित सेट]] को कुल क्रम निर्दिष्ट करके और उपसमुच्चय को अनुक्रम बढ़ते और घटते में परिवर्तित करके दिए गए परिमित सेट के [[सबसेट]] का आदेश देता है, जिसके लिए लेक्सिकोोग्राफ़िकल ऑर्डर लागू होता है।
-एक सामान्यीकरण आंशिक रूप से ऑर्डर किए गए सेट के कार्टेशियन उत्पाद पर ऑर्डर को परिभाषित करता है; यह ऑर्डर कुल ऑर्डर है यदि  और एकमात्र  यदि  कार्तीय उत्पाद के सभी कारक पूरी प्रकार से ऑर्डर किए गए हैं।
+एक सामान्यीकृती पूंजीत आदेशित सेटों के कार्टेशियन उत्पाद पर एक आदेश परिभाषित करती है; यह आदेश एक पूर्ण आदेश होता है यदि और केवल यदि कार्टेशियन उत्पाद के सभी अंश पूर्ण रूप से आदेशित होते हैं।
 == प्रेरणा और परिभाषा ==
@@ Line 15: / Line 14: @@
 [[शब्दकोश]] में शब्द (किसी भाषा में प्रयुक्त शब्दों का सेट) का एक पारंपरिक क्रम होता है, जिसका उपयोग शब्दकोशों और [[विश्वकोषों]] में किया जाता है, जो शब्दों के निर्माण के लिए प्रयुक्त प्रतीकों के वर्णमाला के अंतर्निहित क्रम पर निर्भर करता है। शाब्दिक क्रम अंतर्निहित प्रतीकों के क्रम को देखते हुए शब्द क्रम को औपचारिक बनाने का एक प्रणाली है।
-औपचारिक धारणा परिमित सेट से प्रारंभ होती है {{math|''A''}}, जिसे अधिकांशतः वर्णमाला (औपचारिक भाषा) कहा जाता है, जो पूरी प्रकार से आदेशित है। अर्थात किन्हीं दो प्रतीकों के लिए {{math|''a''}} और {{math|''b''}} में {{math|''A''}} जो समान प्रतीक भी नहीं हैं {{math|''a'' < ''b''}} या {{math|''b'' < ''a''}}.
+इस संरचना का आरंभ एक सीमित सेट {{math|''A''}},के साथ होता है, जिसे अक्सर वर्णमाला कहा जाता है, जो पूर्ण आदेशित होता है। अर्थात्,{{math|''A''}} में दो सिंबल {{math|''a''}} और {{math|''b''}} जो कि एक जैसे नहीं होते हैं, के लिए या तो  {{math|''a'' < ''b''}} होता है या फिर {{math|''b'' < ''a''}} होता है।
-के शब्द {{math|''A''}} प्रतीकों के परिमित अनुक्रम हैं {{math|''A''}}, लंबाई 1 के शब्दों सहित एक एकल प्रतीक, लंबाई 2 के शब्द 2 प्रतीकों के साथ, और इसी प्रकार, यहां तक कि खाली अनुक्रम सहित <math>\varepsilon</math> बिना किसी प्रतीक के। इन सभी परिमित शब्दों के सेट पर लेक्सिकोोग्राफ़िक क्रम शब्दों को निम्नानुसार आदेश देता है:
+{{math|''A''}} के शब्द,शब्द {{math|''A''}} के सिंबलों से बने सिंक्रोनस तार के समान निर्धारित होते हैं, जिनमें एक सिंबल के लिए लंबाई 1 का शब्द, दो सिंबलों के लिए लंबाई 2 का शब्द और इस तरह से आगे बढ़ते हैं, शून्य सिंदूर समेत सभी सीमित संख्याओं के शब्दों को भी शामिल करते हुए। इन सभी सीमित शब्दों के सेट पर लेक्सिकोग्राफिक आदेश शब्दों को
 # एक ही लंबाई के दो अलग-अलग शब्दों को देखते हुए कहें {{math|''a'' {{=}} ''a''<sub>1</sub>''a''<sub>2</sub>...''a''<sub>''k''</sub>}} और {{math|''b'' {{=}} ''b''<sub>1</sub>''b''<sub>2</sub>...''b''<sub>''k''</sub>}}, दो शब्दों का क्रम पहले स्थान पर प्रतीकों के वर्णमाला क्रम पर निर्भर करता है {{math|''i''}} जहां दो शब्द भिन्न होते हैं (शब्दों की प्रारंभ से गिनती):  {{math|''a'' < ''b''}} यदि  और एकमात्र  यदि  {{math|''a''<sub>''i''</sub> < ''b''<sub>''i''</sub>}} वर्णमाला के अंतर्निहित क्रम में {{math|''A''}}.
-# यदि दो शब्दों की लंबाई अलग-अलग है, तो सामान्य शब्दावली क्रम छोटे वाले को रिक्त स्थान के साथ पैड करता है (एक विशेष प्रतीक जिसे प्रत्येक तत्व से छोटा माना जाता है {{math|''A''}}) शब्दों की लंबाई समान होने तक अंत में, और फिर शब्दों की समानता  पिछले स्थितियों की प्रकार की जाती है।
+# यदि दो शब्दों की लम्बाई अलग-अलग है, तो सामान्यतया लेक्सिकोग्राफिकल आदेश छोटे शब्द को "ब्लैंक" (एक विशेष प्रतीक जो {{math|''A''}} के हर तत्व से छोटा माना जाता है) से भर देता है जिससे कि शब्दों की लम्बाई समान हो जाती है, फिर शब्दों की तुलना पिछले मामले की तरह की जाती है।
-चूंकि, कॉम्बिनेटरिक्स में, दूसरे स्थितियों के लिए अधिकांशतः एक और सम्मेलन का उपयोग किया जाता है, जिससे एक छोटा अनुक्रम हमेशा एक लंबे अनुक्रम से छोटा होता है। लेक्सिकोोग्राफिक ऑर्डर के इस प्रकार को कभी-कभी कहा जाता है {{em|[[shortlex order]]}}.
+कॉम्बिनेटरिक्स में, दूसरे स्थितियों के लिए अधिकांशतः एक और सम्मेलन का उपयोग किया जाता है, जिससे एक छोटा अनुक्रम हमेशा एक लंबे अनुक्रम से छोटा होता है। लेक्सिकोोग्राफिक ऑर्डर के इस प्रकार को कभी-कभी कहा जाता है {{em|[[शॉर्टलेक्स ऑर्डर]]}}.
 शब्दावली क्रम में, थॉमस शब्द थॉम्पसन से पहले प्रकट होता है क्योंकि वे पहले पांचवें अक्षर ('ए' और 'पी') में भिन्न होते हैं, और अक्षर 'ए' वर्णमाला में 'पी' अक्षर से पहले आता है। क्योंकि यह पहला अंतर है, इस स्थितियों में 5वां अक्षर वर्णमाला क्रम के लिए सबसे महत्वपूर्ण अंतर है।
@@ Line 40: / Line 39: @@
 लेक्सिकोग्राफिक ऑर्डरिंग के गैर-शब्दकोश उपयोग का एक और उदाहरण [[आईएसओ 8601]] मानक में तारीखों के लिए प्रकट होता है, जो YYYY-MM-DD के रूप में एक तारीख को व्यक्त करता है। इस स्वरूपण योजना का यह लाभ है कि वर्णों के अनुक्रमों पर लेक्सिकोग्राफ़िकल क्रम, जो तारीखों का प्रतिनिधित्व करते हैं, कालानुक्रमिक क्रम के साथ मेल खाता है: पहले की सीई तिथि 9999 वर्ष तक की बाद की तारीख की समानता  में लेक्सिकोग्राफ़िकल क्रम में छोटी होती है। एक अलग [[छँटाई एल्गोरिथ्म]] की आवश्यकता से बचना आसान है।
-== शब्दों का मोनोइड == {{em|monoid of words}ds}} एक वर्णमाला पर {{math|''A''}} [[मुक्त मोनोइड]] ओवर है {{math|''A''}}. अर्थात्, मोनॉइड के तत्व तत्वों के परिमित अनुक्रम (शब्द) हैं {{math|''A''}} (लंबाई 0 के खाली अनुक्रम सहित), और संक्रिया (गुणा) शब्दों का संयोजन है। शब्द {{math|''u''}} दूसरे शब्द का [[उपसर्ग (कंप्यूटर विज्ञान)]] (या 'ट्रंकेशन') है {{math|''v''}} यदि कोई शब्द सम्मलित है {{math|''w''}} ऐसा है कि {{math|1=''v'' = ''uw''}}. इस परिभाषा से, खाली शब्द (<math>\varepsilon</math>) प्रत्येक शब्द का एक उपसर्ग है, और प्रत्येक शब्द स्वयं का एक उपसर्ग है (के साथ {{math|''w''}} <math> = \varepsilon</math>); यदि  इन स्थितियों को बाहर रखा जाना है तो सावधानी बरतनी चाहिए।
+== शब्दों का मोनोइड == {{em|मोनोइड ऑफ वर्ड्स} डी.एस}} एक वर्णमाला पर {{math|''A''}} [[मुक्त मोनोइड]] ओवर है {{math|''A''}}. अर्थात्, मोनॉइड के तत्व तत्वों के परिमित अनुक्रम (शब्द) हैं {{math|''A''}} (लंबाई 0 के खाली अनुक्रम सहित), और संक्रिया (गुणा) शब्दों का संयोजन है। शब्द {{math|''u''}} दूसरे शब्द का [[उपसर्ग (कंप्यूटर विज्ञान)]] (या 'ट्रंकेशन') है {{math|''v''}} यदि कोई शब्द सम्मलित है {{math|''w''}} ऐसा है कि {{math|1=''v'' = ''uw''}}. इस परिभाषा से, खाली शब्द (<math>\varepsilon</math>) प्रत्येक शब्द का एक उपसर्ग है, और प्रत्येक शब्द स्वयं का एक उपसर्ग है (के साथ {{math|''w''}} <math> = \varepsilon</math>); यदि  इन स्थितियों को बाहर रखा जाना है तो सावधानी बरतनी चाहिए।
 इस शब्दावली के साथ, शब्दावली क्रम की उपरोक्त परिभाषा अधिक संक्षिप्त हो जाती है: [[आंशिक आदेश]] या [[कुल आदेश]] सेट को देखते हुए {{math|''A''}}, और दो शब्द {{math|''a''}} और {{math|''b''}} ऊपर {{math|''A''}} ऐसा है कि {{math|''b''}} खाली नहीं है, तो किसी के पास है {{math|''a'' < ''b''}} शब्दकोषीय क्रम के अनुसार , यदि निम्न में से कम से कम एक स्थिति संतुष्ट होती है:
@@ Line 54: / Line 53: @@
 यदि  <math>\,<\,</math> पर कुल आदेश है <math>A,</math> तो शब्दों पर शब्दकोष क्रम है <math>A.</math> चूंकि, सामान्यतः यह एक अच्छा क्रम नहीं है, के होने पर भी  वर्णमाला हो <math>A</math> सुव्यवस्थित है। उदाहरण के लिए, यदि  {{math|1=''A'' = {''a'', ''b''}{{void}}}}, [[औपचारिक भाषा]] {{math|{''a''<sup>''n''</sup>''b'' {{!}} ''n'' ≥ 0, ''b'' > ''ε''}{{void}}}} कोश के क्रम में कोई कम से कम तत्व नहीं है: {{math|... < ''aab'' < ''ab'' < ''b''}}.
-चूंकि कई अनुप्रयोगों के लिए अच्छी प्रकार से ऑर्डर की आवश्यकता होती है, लेक्सिकोोग्राफिक ऑर्डर का एक प्रकार अधिकांशतः उपयोग किया जाता है। यह अच्छी व्यवस्था, जिसे कभी-कभी कहा जाता है {{em|[[shortlex]]}} या {{em|quasi-lexicographical order}}, पहले शब्दों की लंबाई पर विचार करना सम्मलित है (यदि {{math|length(''a'') < length(''b'')}}, तब <math>a < b</math>), और, यदि लंबाई समान हैं, तो शब्दकोषीय क्रम का उपयोग करते हुए। यदि आदेश चालू है {{math|''A''}} एक वेल-ऑर्डर है, शॉर्टलेक्स ऑर्डर के लिए भी यही सच है।<ref name="BaaderNipkow1999"/><ref>{{cite book | last=Calude | first=Cristian | author-link=Cristian S. Calude | title=सूचना और यादृच्छिकता। एक एल्गोरिथम परिप्रेक्ष्य| url=https://archive.org/details/informationrando00calu_163 | url-access=limited | series=EATCS Monographs on Theoretical Computer Science | publisher=[[Springer-Verlag]] | year=1994 | isbn=3-540-57456-5 | zbl=0922.68073 | page=[https://archive.org/details/informationrando00calu_163/page/n19 1] }}</ref>
+चूंकि कई अनुप्रयोगों के लिए अच्छी प्रकार से ऑर्डर की आवश्यकता होती है, लेक्सिकोोग्राफिक ऑर्डर का एक प्रकार अधिकांशतः उपयोग किया जाता है। यह अच्छी व्यवस्था, जिसे कभी-कभी कहा जाता है {{em|[[शॉर्टलेक्स]]}} या {{em|अर्ध-शब्दकोशीय क्रम}}, पहले शब्दों की लंबाई पर विचार करना सम्मलित है (यदि {{math|length(''a'') < length(''b'')}}, तब <math>a < b</math>), और, यदि लंबाई समान हैं, तो शब्दकोषीय क्रम का उपयोग करते हुए। यदि आदेश चालू है {{math|''A''}} एक वेल-ऑर्डर है, शॉर्टलेक्स ऑर्डर के लिए भी यही सच है।<ref name="BaaderNipkow1999"/><ref>{{cite book | last=Calude | first=Cristian | author-link=Cristian S. Calude | title=सूचना और यादृच्छिकता। एक एल्गोरिथम परिप्रेक्ष्य| url=https://archive.org/details/informationrando00calu_163 | url-access=limited | series=EATCS Monographs on Theoretical Computer Science | publisher=[[Springer-Verlag]] | year=1994 | isbn=3-540-57456-5 | zbl=0922.68073 | page=[https://archive.org/details/informationrando00calu_163/page/n19 1] }}</ref>
@@ Line 61: / Line 60: @@
 लेक्सिकोोग्राफ़िकल ऑर्डर ऑर्डर किए गए सेट के कार्टेशियन उत्पाद पर ऑर्डर को परिभाषित करता है, जो कुल ऑर्डर होता है जब ये सभी सेट पूरी प्रकार से ऑर्डर किए जाते हैं। कार्टेशियन उत्पाद का तत्व <math>E_1 \times \cdots \times E_n</math> एक क्रम है जिसका <math>i</math><sup>वें</sup> तत्व का है <math>E_i</math> हर एक के लिए <math>i.</math> अनुक्रमों के लेक्सिकोोग्राफ़िकल ऑर्डर का मूल्यांकन एकमात्र  उन तत्वों की समानता  करता है जिनके अनुक्रमों में समान रैंक है, लेक्सिकोोग्राफ़िकल ऑर्डर ऑर्डर किए गए सेटों के कार्टेशियन उत्पादों तक फैला हुआ है।
-विशेष रूप से, दो आंशिक रूप से आदेशित सेट दिए गए हैं <math>A</math> और <math>B,</math>  {{visible anchor|lexicographical order on the Cartesian product|Lexicographic order on Cartesian products}} <math>A \times B</math> परिभाषित किया जाता है
+विशेष रूप से, दो आंशिक रूप से आदेशित सेट दिए गए हैं <math>A</math> और <math>B,</math>  {{visible anchor|कार्टेशियन उत्पाद पर लेक्सिकोोग्राफिक ऑर्डर|कार्टेशियन उत्पादों पर लेक्सिकोग्राफिक ऑर्डर}} <math>A \times B</math> परिभाषित किया जाता है
 <math display=block>(a, b) \leq \left(a^{\prime}, b^{\prime}\right) \text{ if and only if } a < a^{\prime} \text{ or } \left(a = a^{\prime} \text{ and } b \leq b^{\prime}\right),</math>
 परिणामआंशिक क्रम है। यदि  <math>A</math> और <math>B</math> प्रत्येक कुल आदेश हैं, तो परिणाम कुल आदेश भी होता है। इस प्रकार दो पूरी प्रकार से आदेशित सेटों का शब्दकोषीय क्रम उनके [[उत्पाद क्रम]] का [[रैखिक विस्तार]] है।
@@ Line 76: / Line 75: @@
 == परिमित सबसेट ==
-[[File:Orderings; 6 choose 3.svg|thumb|340px|के 3-उपसमुच्चयों का क्रम <math>\{1, \ldots, 6\},</math> लाल वर्गों के सेट के रूप में प्रतिनिधित्व, अनुक्रम (नीले रंग में), या उनके संकेतक कार्यों  के माध्यम से , दशमलव संकेतन (ग्रे में) में परिवर्तित। ग्रे नंबर भी के सभी सबसेट में सबसेट की रैंक हैं <math>\{1, \ldots, 6\},</math> कोलेक्सिकोग्राफ़िकल ऑर्डर में गिने गए हैं, और 0 से प्रारंभ हो रहे हैं। लेक्सिकोग्राफ़िकल (लेक्स) और कोलेक्सिकोग्राफ़िकल (कोलेक्स) ऑर्डर सबसे ऊपर हैं और संबंधित रिवर्स ऑर्डर (रेव) नीचे हैं<br>एक ऑर्डर से उसके रिवर्स ऑर्डर तक जाता है, या तो ऊपर-नीचे के अतिरिक्त नीचे-ऊपर पढ़कर, या लाल और सफेद रंगों का आदान-प्रदान करके।]]कॉम्बिनेटरिक्स में, किसी को अधिकांशतः गणना करनी होती है, और इसलिए किसी दिए गए सेट के परिमित सबसेट को ऑर्डर करना होता है <math>S.</math> इसके लिए, सामान्यतः एक ऑर्डर चुनता है <math>S.</math> फिर, सबसेट [[छँटाई]] <math>S</math> इसे बढ़ते क्रम में बदलने के समान है। परिणामी अनुक्रमों पर लेक्सिकोग्राफ़िक क्रम इस प्रकार उपसमुच्चय पर आदेश उत्पन्न करता है, जिसे भी कहा जाता है {{em|lexicographical order}}.
+[[File:Orderings; 6 choose 3.svg|thumb|340px|के 3-उपसमुच्चयों का क्रम <math>\{1, \ldots, 6\},</math> लाल वर्गों के सेट के रूप में प्रतिनिधित्व, अनुक्रम (नीले रंग में), या उनके संकेतक कार्यों  के माध्यम से , दशमलव संकेतन (ग्रे में) में परिवर्तित। ग्रे नंबर भी के सभी सबसेट में सबसेट की रैंक हैं <math>\{1, \ldots, 6\},</math> कोलेक्सिकोग्राफ़िकल ऑर्डर में गिने गए हैं, और 0 से प्रारंभ हो रहे हैं। लेक्सिकोग्राफ़िकल (लेक्स) और कोलेक्सिकोग्राफ़िकल (कोलेक्स) ऑर्डर सबसे ऊपर हैं और संबंधित रिवर्स ऑर्डर (रेव) नीचे हैं<br>एक ऑर्डर से उसके रिवर्स ऑर्डर तक जाता है, या तो ऊपर-नीचे के अतिरिक्त नीचे-ऊपर पढ़कर, या लाल और सफेद रंगों का आदान-प्रदान करके।]]कॉम्बिनेटरिक्स में, किसी को अधिकांशतः गणना करनी होती है, और इसलिए किसी दिए गए सेट के परिमित सबसेट को ऑर्डर करना होता है <math>S.</math> इसके लिए, सामान्यतः एक ऑर्डर चुनता है <math>S.</math> फिर, सबसेट [[छँटाई]] <math>S</math> इसे बढ़ते क्रम में बदलने के समान है। परिणामी अनुक्रमों पर लेक्सिकोग्राफ़िक क्रम इस प्रकार उपसमुच्चय पर आदेश उत्पन्न करता है, जिसे भी कहा जाता है {{em|लेक्सिकोग्राफिक ऑर्डर}}.
 इस संदर्भ में, सामान्यतः पहले सबसेट को [[प्रमुखता]]  के माध्यम से  सॉर्ट करना पसंद करते हैं, जैसे शॉर्टलेक्स ऑर्डर में। इसलिए, निम्नलिखित में, हम निश्चित कार्डिनल के सबसेट पर एकमात्र  आदेश पर विचार करेंगे।
@@ Line 85: / Line 84: @@
 ::{{math|234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456}}.
-[[प्राकृतिक संख्या]]ओं की दी गई कार्डिनैलिटी के परिमित उपसमुच्चयों को क्रमबद्ध करने के लिए, {{em|colexicographical}} ऑर्डर (नीचे देखें) अधिकांशतः अधिक सुविधाजनक होता है, क्योंकि सभी [[प्रारंभिक खंड]] परिमित होते हैं, और इस प्रकार कोलेक्सिकोोग्राफिकल ऑर्डर प्राकृतिक संख्याओं और सेट के सेट के बीच [[ आदेश समरूपता ]] को परिभाषित करता है <math>n</math> प्राकृतिक संख्या। लेक्सिकोग्राफिक ऑर्डर के लिए यह स्थिति नहीं है, जैसा कि लेक्सिकोोग्राफिक ऑर्डर के साथ, हमारे पास है, उदाहरण के लिए, <math>12 n < 134</math> हर एक के लिए <math>n > 2.</math>
+[[प्राकृतिक संख्या]]ओं की दी गई कार्डिनैलिटी के परिमित उपसमुच्चयों को क्रमबद्ध करने के लिए, {{em|कोलेक्सिकोग्राफिक}} ऑर्डर (नीचे देखें) अधिकांशतः अधिक सुविधाजनक होता है, क्योंकि सभी [[प्रारंभिक खंड]] परिमित होते हैं, और इस प्रकार कोलेक्सिकोोग्राफिकल ऑर्डर प्राकृतिक संख्याओं और सेट के सेट के बीच [[ आदेश समरूपता ]] को परिभाषित करता है <math>n</math> प्राकृतिक संख्या। लेक्सिकोग्राफिक ऑर्डर के लिए यह स्थिति नहीं है, जैसा कि लेक्सिकोोग्राफिक ऑर्डर के साथ, हमारे पास है, उदाहरण के लिए, <math>12 n < 134</math> हर एक के लिए <math>n > 2.</math>
@@ Line 142: / Line 141: @@
 इन स्वीकार्य आदेशों में से एक लेक्सिकोग्राफिक ऑर्डर है। यह, ऐतिहासिक रूप से, सबसे पहले ग्रोबनेर ठिकानों को परिभाषित करने के लिए उपयोग किया गया है, और इसे कभी-कभी कहा जाता है {{em|pure lexicographical order}} इसे अन्य आदेशों से अलग करने के लिए जो कि एक शब्दावली क्रम से भी संबंधित होती है।
-दूसरे में पहले कुल डिग्रियों की समानता  करना और फिर लेक्सिकोोग्राफिक क्रम का उपयोग करके संघर्षों को हल करना सम्मलित है। इस आदेश का व्यापक रूप से उपयोग नहीं किया जाता है, क्योंकि या तो लेक्सिकोग्राफ़िकल ऑर्डर या डिग्री रिवर्स लेक्सिकोग्राफ़िकल ऑर्डर में सामान्यतः उत्तम गुण होते हैं। वह {{em|degree reverse lexicographical order}} पहले कुल डिग्रियों की समानता  करने में भी सम्मलित है, और कुल डिग्रियों की समानता के स्थितियों में, कोलेक्सिकोग्राफ़िक ऑर्डर के रिवर्स का उपयोग करते हुए। अर्थात्, दो घातांक सदिश दिए गए हैं, एक के पास
+दूसरे में पहले कुल डिग्रियों की समानता  करना और फिर लेक्सिकोोग्राफिक क्रम का उपयोग करके संघर्षों को हल करना सम्मलित है। इस आदेश का व्यापक रूप से उपयोग नहीं किया जाता है, क्योंकि या तो लेक्सिकोग्राफ़िकल ऑर्डर या डिग्री रिवर्स लेक्सिकोग्राफ़िकल ऑर्डर में सामान्यतः उत्तम गुण होते हैं। वह {{em|डिग्री रिवर्स लेक्सिकोग्राफिक ऑर्डर}} पहले कुल डिग्रियों की समानता  करने में भी सम्मलित है, और कुल डिग्रियों की समानता के स्थितियों में, कोलेक्सिकोग्राफ़िक ऑर्डर के रिवर्स का उपयोग करते हुए। अर्थात्, दो घातांक सदिश दिए गए हैं, एक के पास
 <math display=block>[a_1, \ldots, a_n] < [b_1, \ldots, b_n]</math>
 या तो

Anonymous

Search

लेक्सिकोग्राफिक ऑर्डर: Difference between revisions

Namespaces

More

Page actions

Revision as of 15:58, 30 March 2023

Contents

प्रेरणा और परिभाषा

अंक प्रणाली और दिनांक

कार्टेशियन उत्पाद

परिमित सबसेट

जेड के समूह आदेश^एन

शब्दकोश क्रम

एकपद

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

लेक्सिकोग्राफिक ऑर्डर: Difference between revisions

Revision as of 15:58, 30 March 2023

प्रेरणा और परिभाषा

अंक प्रणाली और दिनांक

कार्टेशियन उत्पाद

परिमित सबसेट

जेड के समूह आदेशएन

शब्दकोश क्रम

एकपद

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories

जेड के समूह आदेश^एन