लेक्सिकोग्राफिक ऑर्डर

For similarly named ordering systems outside mathematics, see alphabetical order, natural sort order, lexicographic preferences, and collation.

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

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

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

एक सामान्यीकरण आंशिक रूप से ऑर्डर किए गए सेट के कार्टेशियन उत्पाद पर ऑर्डर को परिभाषित करता है; यह ऑर्डर कुल ऑर्डर है यदि और एकमात्र यदि कार्तीय उत्पाद के सभी कारक पूरी प्रकार से ऑर्डर किए गए हैं।

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

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

औपचारिक धारणा परिमित सेट से प्रारंभ होती है A, जिसे अधिकांशतः वर्णमाला (औपचारिक भाषा) कहा जाता है, जो पूरी प्रकार से आदेशित है। अर्थात किन्हीं दो प्रतीकों के लिए a और b में A जो समान प्रतीक भी नहीं हैं a < b या b < a.

के शब्द A प्रतीकों के परिमित अनुक्रम हैं A, लंबाई 1 के शब्दों सहित एक एकल प्रतीक, लंबाई 2 के शब्द 2 प्रतीकों के साथ, और इसी प्रकार, यहां तक ​​कि खाली अनुक्रम सहित $\varepsilon$ बिना किसी प्रतीक के। इन सभी परिमित शब्दों के सेट पर लेक्सिकोोग्राफ़िक क्रम शब्दों को निम्नानुसार आदेश देता है:

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

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

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

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

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

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

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

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

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

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

== शब्दों का मोनोइड == monoid of words}ds एक वर्णमाला पर 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ⁿb | n ≥ 0, b > ε} कोश के क्रम में कोई कम से कम तत्व नहीं है: ... < aab < ab < b.

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

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

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

विशेष रूप से, दो आंशिक रूप से आदेशित सेट दिए गए हैं $A$ और $B,$ lexicographical order on the Cartesian product $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... > ... एक अनंत अवरोही श्रृंखला है। इसी प्रकार, अनंत लेक्सिकोग्राफिक उत्पाद नोथेरियन संबंध भी नहीं है क्योंकि 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$ इसे बढ़ते क्रम में बदलने के समान है। परिणामी अनुक्रमों पर लेक्सिकोग्राफ़िक क्रम इस प्रकार उपसमुच्चय पर आदेश उत्पन्न करता है, जिसे भी कहा जाता है lexicographical order.

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

उदाहरण के लिए, पूर्णांकों के प्राकृतिक क्रम का उपयोग करते हुए, तीन तत्वों के सबसेट पर लेक्सिकोोग्राफिक ऑर्डरिंग $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.

प्राकृतिक संख्याओं की दी गई कार्डिनैलिटी के परिमित उपसमुच्चयों को क्रमबद्ध करने के लिए, colexicographical ऑर्डर (नीचे देखें) अधिकांशतः अधिक सुविधाजनक होता है, क्योंकि सभी प्रारंभिक खंड परिमित होते हैं, और इस प्रकार कोलेक्सिकोोग्राफिकल ऑर्डर प्राकृतिक संख्याओं और सेट के सेट के बीच आदेश समरूपता को परिभाषित करता है $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}.$ वास्तव में, $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₁a₂...a_k <^lex b₁b₂ ... b_k यदि a_i < b_i पहले के लिए i कहाँ a_i और b_i अलग होना,

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

a₁a₂...a_k <^colex b₁b₂...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 < ....

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

एकपद

Main article: मोनोमियल ऑर्डर

बहुपदों पर विचार करते समय, शर्तों का क्रम सामान्य रूप से कोई फर्क नहीं पड़ता, क्योंकि जोड़ क्रमविनिमेय है। चूंकि, कुछ कलन विधि, जैसे कि बहुपद लंबे विभाजन, को एक विशिष्ट क्रम में शब्दों की आवश्यकता होती है। बहुभिन्नरूपी बहुपदों के लिए कई मुख्य एल्गोरिदम ग्रोबनर आधारों से संबंधित हैं, अवधारणा जिसके लिए एक मोनोमियल ऑर्डर की पसंद की आवश्यकता होती है, जो कुल ऑर्डर है, जो एकपदीयों की मोनोइड संरचना के साथ संगत है। यहाँ संगत का अर्थ है $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 इसे अन्य आदेशों से अलग करने के लिए जो कि एक शब्दावली क्रम से भी संबंधित होती है।

दूसरे में पहले कुल डिग्रियों की समानता करना और फिर लेक्सिकोोग्राफिक क्रम का उपयोग करके संघर्षों को हल करना सम्मलित है। इस आदेश का व्यापक रूप से उपयोग नहीं किया जाता है, क्योंकि या तो लेक्सिकोग्राफ़िकल ऑर्डर या डिग्री रिवर्स लेक्सिकोग्राफ़िकल ऑर्डर में सामान्यतः उत्तम गुण होते हैं। वह degree reverse 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].$$

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

यह भी देखें

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

बाहरी संबंध

• Learning materials related to Lexicographic and colexicographic order at Wikiversity