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

Revision as of 19:10, 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},$ वर्गीकरण के लिए)।

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

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

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

[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 39: / Line 39: @@
 लेक्सिकोग्राफिक ऑर्डरिंग के गैर-शब्दकोश उपयोग का एक और उदाहरण [[आईएसओ 8601]] मानक में तारीखों के लिए प्रकट होता है, जो YYYY-MM-DD के रूप में एक तारीख को व्यक्त करता है। इस स्वरूपण योजना का यह लाभ है कि वर्णों के अनुक्रमों पर लेक्सिकोग्राफ़िकल क्रम, जो तारीखों का प्रतिनिधित्व करते हैं, कालानुक्रमिक क्रम के साथ मेल खाता है: पहले की सीई तिथि 9999 वर्ष तक की बाद की तारीख की समानता  में लेक्सिकोग्राफ़िकल क्रम में छोटी होती है। एक अलग [[छँटाई एल्गोरिथ्म]] की आवश्यकता से बचना आसान है।
-== शब्दों का मोनोइड == {{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>); यदि  इन स्थितियों को बाहर रखा जाना है तो सावधानी बरतनी चाहिए।
+== शब्दों का मोनोइड ==
+{{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 68: / Line 69: @@
 परिमित स्थितियों के विपरीत, अच्छी प्रकार से ऑर्डर का अनंत उत्पाद लेक्सिकोग्राफ़िकल ऑर्डर  के माध्यम से  आवश्यक  नहीं है। उदाहरण के लिए, अनगिनत अनंत द्विआधारी अनुक्रमों का सेट (परिभाषा के अनुसार, गैर-नकारात्मक पूर्णांक से कार्यों का सेट <math>\{ 0, 1 \},</math> [[कैंटर स्पेस]] के रूप में भी जाना जाता है <math>\{ 0, 1 \}^{\omega}</math>) सुव्यवस्थित नहीं है; अनुक्रमों का उपसमुच्चय जिसमें ठीक है <math>1</math> (वह है, {{math|{ 100000..., 010000..., 001000..., ... }{{void}}}})  के माध्यम से  प्रेरित शब्दकोष क्रम के अनुसार  कम से कम तत्व नहीं है <math>0 < 1,</math> क्योंकि {{math|100000... > 010000... > 001000... > ...}} एक [[अनंत अवरोही श्रृंखला]] है।<ref name="Harzheim">{{cite book|author=Egbert Harzheim|title=ऑर्डर किए गए सेट|year=2006|publisher=Springer|isbn=978-0-387-24222-4|pages=88–89}}</ref> इसी प्रकार, अनंत लेक्सिकोग्राफिक उत्पाद [[नोथेरियन संबंध]] भी नहीं है क्योंकि {{math|011111... < 101111... < 110111 ... < ...}} एक अनंत आरोही श्रृंखला है।
-== एक [[सुव्यवस्थित सेट]] == पर कार्य करता है
+== [[सुव्यवस्थित सेट]] ==
 एक सुव्यवस्थित सेट से कार्य करता है <math>X</math> पूरी प्रकार से ऑर्डर किए गए सेट के लिए <math>Y</math>  के माध्यम से  अनुक्रमित अनुक्रमों से पहचाना जा सकता है <math>X</math> के तत्वों का <math>Y.</math> इस प्रकार उन्हें लेक्सिकोोग्राफिक ऑर्डर और ऐसे दो कार्यों के लिए ऑर्डर दिया जा सकता है <math>f</math> और <math>g,</math> शब्दकोषीय क्रम इस प्रकार सबसे छोटे के लिए उनके मूल्यों  के माध्यम से  निर्धारित किया जाता है <math>x</math> ऐसा है कि <math>f(x) \neq g(x).</math>
 यदि  <math>Y</math> भी सुव्यवस्थित है और <math>X</math> परिमित है, तो परिणामी क्रम अच्छी-व्यवस्था है। जैसा कि ऊपर दिखाया गया है, यदि  <math>X</math> अनंत है ऐसा नहीं है।

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 19:10, 30 March 2023

Contents

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

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

शब्दों का मोनोइड

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

सुव्यवस्थित सेट

परिमित सबसेट

जेड के समूह ऑर्डर^एन

शब्दकोश क्रम

एकपद

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 19:10, 30 March 2023

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

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

शब्दों का मोनोइड

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

सुव्यवस्थित सेट

परिमित सबसेट

जेड के समूह ऑर्डरएन

शब्दकोश क्रम

एकपद

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories

जेड के समूह ऑर्डर^एन