सबसे लंबा बढ़ता उपक्रम (LIS)

किसी सूची से बाएँ से दाएँ संख्याएँ चुनें, हर एक पिछली से बड़ी। ऐसी शृंखला कितनी लंबी हो सकती है? सवाल इतना सरल है कि किसी पहेली की किताब में आ जाए, और इसका उत्तर एक ताश के खेल, गतिशील प्रोग्रामिंग की एक क्लासिक तालिका और यादृच्छिक फेरबदल के बारे में सबसे सुंदर परिणामों में से एक को जोड़ता है।

अलग-अलग ऊँचाई की छड़ों की एक पंक्ति, जिसमें बाएँ से दाएँ ऊपर उठती छड़ों की एक शृंखला नारंगी रंग में दिखाई गई है
अलग-अलग ऊँचाई की छड़ों की एक पंक्ति, जिसमें बाएँ से दाएँ ऊपर उठती छड़ों की एक शृंखला नारंगी रंग में दिखाई गई है

समस्या

संख्याओं की एक सूची दी हो, तो उपक्रम उनमें से कुछ को उनके मूल क्रम में रखता है। अगर हर मान पिछले से बड़ा हो, तो उपक्रम बढ़ता है। सबसे लंबा बढ़ता उपक्रम, यानी LIS, ऐसा सबसे लंबा चुनाव है। n मानों की सूची में 2ⁿ उपक्रम होते हैं, इसलिए सबको जाँचना सिर्फ़ बहुत छोटी सूचियों के लिए चलता है।

तालिका

मान लीजिए len[i] उस सबसे लंबे बढ़ते उपक्रम की लंबाई है जो ठीक स्थान i पर खत्म होता है। यह अकेले मान के लिए 1 है, या किसी ऐसे पिछले स्थान j के लिए 1 + len[j] जिसका मान छोटा हो, इनमें से जो भी सबसे बड़ा हो। हर स्थान सभी पिछले स्थानों को देखता है, इसलिए तालिका को n·(n − 1)/2 तुलनाएँ चाहिए। उत्तर सबसे बड़ा len[i] है, और यह लिखते जाने से कि हर len[i] किस j से मिला, उपक्रम को पीछे से पढ़ा जा सकता है।

एक उदाहरण

3, 10, 2, 1, 20, 4, 6, 7, 5, 9 लें। स्थान दर स्थान लंबाइयाँ 1, 2, 1, 1, 3, 2, 3, 4, 3 और 5 हैं: 20 क्रम 3, 10 को बढ़ाता है; 4 क्रम 3 को; 6 क्रम 4 को, 7 क्रम 6 को, और 9 क्रम 7 को। 9 से पीछे पढ़ने पर 3, 4, 6, 7, 9 मिलता है, लंबाई 5 का एक बढ़ता उपक्रम।

तेज़ तरीका: पेशेंस सॉर्टिंग

मानों को ताश के पत्तों की तरह ढेरों पर बाँटें: हर मान उस सबसे बाएँ ढेर पर जाता है जिसका ऊपरी पत्ता उससे छोटा न हो, या दाईं ओर नया ढेर शुरू करता है। ढेरों की संख्या LIS की लंबाई है। क्योंकि ढेरों के ऊपरी पत्ते हमेशा क्रम में रहते हैं, सही ढेर बाइनरी सर्च से मिल जाता है, इसलिए पूरा तरीका O(n log n) चरण लेता है। इसका नाम उस सॉलिटेयर (पेशेंस) ताश के खेल पर है जिससे यह मिलता-जुलता है।

थोड़ा गणित

1935 में पॉल एर्डोश और जॉर्ज सेकेरेश ने सिद्ध किया कि n² + 1 अलग-अलग संख्याओं की किसी भी सूची में लंबाई n + 1 का एक बढ़ता या घटता उपक्रम होता है। स्तानिस्लाव उलाम ने 1961 में पूछा कि n संख्याओं के एक यादृच्छिक फेरबदल का LIS कितना लंबा होता है। बड़े n के लिए 2√n के करीब वाला उत्तर 1977 में अनातोली वर्शिक और सर्गेई केरोव ने, और बेन लोगन और लैरी शेप ने तय किया, और 1999 में जिन्हो बैक, पर्सी डाइफ़्ट और कुर्ट योहानसन ने इसके उतार-चढ़ाव का सटीक आकार खोजा: रैंडम मैट्रिक्स सिद्धांत का ट्रेसी–विडम वितरण।

1992 में बुडापेस्ट के एक छात्र सेमिनार में पॉल एर्डोस। 1935 में उन्होंने और जॉर्ज सेकेरेश ने सिद्ध किया कि n² + 1 अलग-अलग संख्याओं की हर सूची में लंबाई n + 1 का एक बढ़ता या घटता उप-अनुक्रम होता है।
1992 में बुडापेस्ट के एक छात्र सेमिनार में पॉल एर्डोस। 1935 में उन्होंने और जॉर्ज सेकेरेश ने सिद्ध किया कि n² + 1 अलग-अलग संख्याओं की हर सूची में लंबाई n + 1 का एक बढ़ता या घटता उप-अनुक्रम होता है।
स्तानिस्वाफ़ उलम का चित्र
स्तानिस्वाफ़ उलम का चित्र

खुद आज़माएँ

ऐप खोलें और “आगे” दबाएँ। नारंगी कॉलम वह स्थान है जिस पर काम हो रहा है, और नीला कॉलम वह पिछला स्थान जिससे उसकी तुलना हो रही है। जैसे-जैसे लंबे क्रम मिलते हैं, “लंबाई” पंक्ति बढ़ती है, “किसके बाद” पंक्ति याद रखती है कि वे कहाँ से आए, और अंत में उत्तर नारंगी रंग में पीछे से पढ़ा जाता है और तालिका के नीचे दिखाया जाता है।

अक्सर पूछे जाने वाले प्रश्न

LIS की समय जटिलता क्या है?

तालिका से O(n²), क्योंकि हर स्थान हर पिछले स्थान को देखता है, और पेशेंस सॉर्टिंग व बाइनरी सर्च से O(n log n)। दोनों को O(n) मेमोरी चाहिए।

सबसे लंबा न घटने वाला उपक्रम कैसे ढूँढें?

किसी मान को अपने बराबर मान के बाद आने दें: < की जगह ≤ से तुलना करें। ऐप में “बराबर मानों की अनुमति दें” पर टिक करें। पेशेंस सॉर्टिंग में हर मान को उस सबसे बाएँ ढेर पर रखें जिसका ऊपरी पत्ता उससे सख्ती से बड़ा हो।

सबसे लंबा घटता उपक्रम क्या है?

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

यादृच्छिक सूची का LIS कितना लंबा होता है?

n अलग-अलग संख्याओं के यादृच्छिक फेरबदल के लिए, बड़े n पर 2√n के करीब। सुधार n के छठे मूल की तरह बढ़ता है, इसलिए एक हज़ार संख्याओं के लिए औसत लगभग 58 है, 2√1000 ≈ 63 से थोड़ा कम।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

सबसे लंबा बढ़ता उपक्रम आज़माएँ