शब्दकोषीय क्रम

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

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

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

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

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

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

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

औपचारिक धारणा एक परिमित समुच्चय से शुरू होती है 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 परिमित है (या समकक्ष, प्रत्येक गैर-रिक्त उपसमुच्चय में कम से कम तत्व होता है)। यह सत्य नहीं है कि सभी परिमित शब्दों का समुच्चय सुव्यवस्थित है; उदाहरण के लिए, शब्दों के अनंत सेट {बी, एबी, आब, आआब, ... } में शब्दावली की दृष्टि से कोई प्रारंभिक तत्व नहीं है।

अंक प्रणालियाँ और तिथियाँ

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

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

दशमलव संकेतन में लिखी गई वास्तविक संख्याओं के लिए, शब्दावली क्रम का थोड़ा अलग प्रकार उपयोग किया जाता है: दशमलव बिंदु के बाईं ओर के हिस्सों की तुलना पहले की तरह की जाती है; यदि वे समान हैं, तो दशमलव बिंदु के दाईं ओर के हिस्सों की तुलना शब्दावली क्रम से की जाती है। इस संदर्भ में पैडिंग 'रिक्त' एक पिछला 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.$

Z के समूह आदेशⁿ

होने देना $\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: Monomial order

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