सबसे लंबा सामान्य उपअनुक्रम: Python, C++ उदाहरण

सबसे लम्बा उभयनिष्ठ उपअनुक्रम क्या है?

सबसे लंबा कॉमन सबसीक्वेंस (LCS) का मतलब है कि आपको ऑब्जेक्ट के दो स्ट्रिंग/पैटर्न/सीक्वेंस दिए जाएंगे। इन दो सीक्वेंस/स्ट्रिंग्स में से, आपको दोनों स्ट्रिंग या पैटर्न में मौजूद समान क्रम में तत्वों का सबसे लंबा सबसीक्वेंस ढूंढना होगा।

उदाहरण

उदाहरण के लिए, दो स्ट्रिंग प्रदान की गई हैं।

चलिए मान लेते हैं कि,

पैटर्न_1 = “RGBGARGA”
पैटर्न_2 = “BGRARG”

• पैटर्न_1 से, “RGB”, “RGGA”, “RGAR” जैसे अनुक्रम बनाए जा सकते हैं। अनुक्रम बनाने के लिए, आपको स्ट्रिंग में प्रत्येक वर्ण की सापेक्ष स्थिति बनाए रखने की आवश्यकता है।
• पैटर्न_2 से, हम “BGR”, “BRAG”, “RARG” जैसे अनुक्रम बना सकते हैं। अनुक्रम तब तक बनाए जा सकते हैं जब तक वे मूल स्ट्रिंग की सापेक्ष स्थिति को बनाए रखते हैं।

सापेक्ष स्थिति शब्द का अर्थ है क्रम।

उदाहरण के लिए, “BRG” एक वैध अनुक्रम है क्योंकि मूल स्ट्रिंग पैटर्न_2 में “B” पहले आया, फिर “R” और फिर “G”। हालाँकि, यदि कोई अनुक्रम “RBRG” है, तो यह वैध नहीं है। क्योंकि मूल स्ट्रिंग (पैटर्न_2) में, “B” पहले आता है।

दिए गए दो अनुक्रमों या सारणी से सबसे लंबा सामान्य उपअनुक्रम खोजने के लिए हमारे पास दो विकल्प हैं।

• सरल विधि
• डायनेमिक प्रोग्रामिंग समाधान: सबसे लंबा कॉमन सबसीक्वेंस को LCS के रूप में भी जाना जाता है।

एक सरल समाधान में समय की जटिलता अधिक होती है और यह इष्टतम समाधान नहीं है। डायनेमिक प्रोग्रामिंग समाधान (DP) का उपयोग करके, हम जटिलता की समस्या पर काबू पा लेते हैं।

सरल विधि

सरल विधि, समय जटिलता और अन्य अनुकूलन कारकों की परवाह किए बिना समस्या के लिए एक सरल दृष्टिकोण है।

अधिकांश मामलों में नैवे विधि में "ब्रूट फोर्स", कई लूप, पुनरावर्ती विधियां शामिल होती हैं।

ब्रूट फोर्स शब्द का अर्थ है किसी समस्या के लिए सभी संभावित पैटर्नों का प्रयोग करना।

उदाहरण

पैटर्न1 और पैटर्न2 के उपरोक्त उदाहरण से, मान लें कि पैटर्न1 की लंबाई m है और पैटर्न2 की लंबाई n है। हर संभावित मामले की जाँच करने के लिए, हमें पैटर्न1 के साथ पैटर्न2 के हर संभावित उप-अनुक्रम का मूल्यांकन करने की आवश्यकता है।

यहाँ एक सरल 4 अक्षर की स्ट्रिंग "ABCD" है। उदाहरण के लिए, हमें "ABCD" से एक अनुक्रम बनाने की आवश्यकता है। या तो हम एक वर्ण ले सकते हैं या नहीं। इसका मतलब है कि, प्रत्येक वर्ण के लिए, हमारे पास दो विकल्प हैं।

वे हैं:

• वर्ण को उपअनुक्रम में जोड़ दिया जाएगा।
• वर्ण को उपअनुक्रम में नहीं जोड़ा जाएगा।

यहां, चित्र उन सभी अनुक्रमों को दर्शाते हैं जिन्हें हम स्ट्रिंग “ABCD” से बना सकते हैं।

1 वर्ण वाला अनुक्रम:

2 वर्णों वाले अनुक्रम:

3 वर्णों वाले अनुक्रम:

ऊपर दिए गए आरेख से पता चलता है कि 14 अनुक्रम हैं। यदि हम अक्षर नहीं लेते हैं, मूल रूप से एक खाली स्ट्रिंग, तो कुल अनुक्रम 15 होंगे। इसके अलावा, स्ट्रिंग “ABCD” स्वयं एक अनुक्रम है। इसलिए, कुल अनुक्रम 16 हैं।

तो, 2 उत्पन्न करना संभव है⁴ या “ABCD” से 16 उप-अनुक्रम। फिर, लंबाई वाली एक स्ट्रिंग m कुल अनुक्रम 2 होना चाहिए^m.

प्रत्येक उप-अनुक्रम के लिए, हमें पूरे पैटर्न2 के लिए इसकी जाँच करनी होगी। इसमें 0(n) समय लगेगा। 0(n) का अर्थ है जटिलता फ़ंक्शन जो निष्पादन के लिए लगने वाले समय की गणना करता है।

तो, कुल समय जटिलता बन जाती है ओ(एन*2^m). उदाहरण के लिए, हमने ऊपर m=8 और n=5 का मान देखा है।

नैवे विधि के चरण इस प्रकार हैं:

चरण 1) पैटर्न 1 से एक अनुक्रम लें।
चरण 2) चरण 1 के अनुक्रम को पैटर्न 2 से मिलाएं।
चरण 3) यदि यह मेल खाता है, तो उपअनुक्रम को सहेजें।
चरण 4) यदि पैटर्न 1 में अधिक अनुक्रम शेष रह गया है, तो पुनः चरण 1 पर जाएँ।
चरण 5) सबसे लंबे उपअनुक्रम को प्रिंट करें.

इष्टतम निर्माण

इष्टतम उपसंरचना शब्द का अर्थ है कि उपसमस्याओं को हल करके एक इष्टतम समाधान (सरल) पाया जा सकता है। उदाहरण के लिए, उपरोक्त उदाहरण में, हमारे पास पैटर्न1 और पैटर्न2 हैं।

चरण 1) प्रत्येक पैटर्न से पहले दो अक्षर लें

चरण 2) प्रत्येक पैटर्न से तीसरे से पांचवें अक्षर लें।

चरण 3) शेष वर्णों के साथ भी इसी प्रकार आगे बढ़ें।

हम सब-स्ट्रिंग (मूल स्ट्रिंग से उत्पन्न स्ट्रिंग) पर LCS पाते हैं। फिर हम सब-स्ट्रिंग की LCS की लंबाई का रिकॉर्ड रखते हैं।

अब, यहाँ एक और दिलचस्प संपत्ति है जो अतिव्यापी उप-समस्याएँकिसी समस्या में अतिव्यापी उप-समस्याएं तब कही जाती हैं जब समस्या कथन को छोटी उप-समस्याओं में तोड़ा जा सके और प्रोग्राम में कई बार उपयोग किया जा सके।

नीचे दिया गया चित्र दर्शाता है कि पुनरावर्ती एल्गोरिथ्म ने समान पैरामीटर वाले फ़ंक्शन को कई बार कॉल किया।

उदाहरण के लिए, आइए हम पुनरावर्तन वृक्ष को देखें।

गहरे रंग के बॉक्स में, आप ओवरलैपिंग उप-समस्याओं को देख सकते हैं। (“आरजी”, “आरए”), (“आरजी”, “आर”) और अन्य को कई बार बुलाया जाता है।

इसे अनुकूलित करने के लिए, हमारे पास निम्न दृष्टिकोण है गतिशील प्रोग्रामिंग (डीपी)

सबसे लंबे संचार अनुक्रम की पुनरावर्ती विधि

ऊपर दिखाया गया ग्राफ पुनरावर्ती विधि है। प्रत्येक पुनरावर्ती फ़ंक्शन में पुनरावृत्ति को तोड़ने या अपने स्टैक से वापस लौटना शुरू करने के लिए एक आधार मामला होता है।

इस कार्यान्वयन के लिए, हम एक आधार मामले का उपयोग करेंगे। तो, कलन विधि निम्नलिखित जैसा है:

• यदि अंतिम तत्व से पहले के सभी तत्व मेल खाते हैं, तो लंबाई को एक से बढ़ाएं और वापस लौटें
• फ़ंक्शन में दो पैटर्न पास करें, और रिटर्न का अधिकतम मान लें
• यदि एक पैटर्न की लंबाई शून्य है, तो हमारे पास तुलना करने के लिए कोई उप-अनुक्रम नहीं है। इस मामले में 0 लौटाएँ। यह रिकर्सन का आधार मामला है।

छद्म कोड:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of lcs(pattern_1, pattern_2, len_1 - 1, len_2),
    lcs(pattern_1, pattern_2, len_1, len_2 - 1)

कार्यान्वयन C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

आउटपुट:

Length of LCS is: 5

पायथन में कार्यान्वयन

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
    return 0
if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
else :
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1))
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

आउटपुट:

Lenght of LCS is:  5

सबसे लंबे कॉमन सबसीक्वेंस (LCS) की डायनेमिक प्रोग्रामिंग विधि

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

हम mxn आयाम वाली 2D सारणी का उपयोग करेंगे, जहाँ m और n पैटर्न1 और पैटर्न2 की लंबाइयाँ हैं।

के लिए 2डी सरणी, हम पायथन में सूची डेटा संरचनाओं या वेक्टर/सरणी डेटा संरचनाओं का उपयोग कर सकते हैं C++.

DP का उपयोग करते हुए LCS के लिए छद्म कोड:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
n = length of pattern_2 + 1
dp[n][m]
for i in range 0 to n + 1:
    for j in range 0 to m + 1:
    if i or j equals to 0:
    dp[i][j] = 0
else if pattern_1[i] == pattern_2[j]:
    dp[i]][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]

यहां LCS तालिका दी गई है जिसका उपयोग गतिशील प्रोग्रामिंग दृष्टिकोण के लिए 2D सरणी डेटा संरचना के रूप में किया जाता है।

आइये यहाँ इस्तेमाल किए गए तर्क पर चर्चा करें। चरण इस प्रकार हैं:

चरण 1) यदि i या j शून्य है, तो हम दिए गए दो स्ट्रिंग से एक खाली स्ट्रिंग ले रहे हैं और सामान्य उप-अनुक्रम खोजने की कोशिश कर रहे हैं। हालाँकि, चूँकि हम जो उप-स्ट्रिंग ले रहे हैं वह खाली है, इसलिए उप-अनुक्रम की लंबाई 0 है।

चरण 2) यदि दो वर्ण मेल खाते हैं, तो हम पहले से गणना किए गए LCS को बढ़ाकर (i,j) इंडेक्स को मान प्रदान करेंगे, जो (i-1,j-1) इंडेक्स (पिछली पंक्ति से) में मौजूद है।

चरण 3) यदि यह मेल नहीं खाता है, तो हम आसन्न दो इंडेक्स का अधिकतम LCS लेंगे। और इस तरह, हमें 2D सरणी में सभी मान भरने होंगे।

चरण 4) अंत में, हम 2D सारणी के अंतिम सेल का मान लौटाएंगे।

मूल रूप से, 2D सरणी में सभी मान में सामान्य उप-अनुक्रम की लंबाई शामिल होती है। इनमें से, अंतिम सेल में सबसे लंबे सामान्य उप-अनुक्रम की लंबाई होती है।

कार्यान्वयन C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i & lt; n + 1; i++) {
    for (int j = 0; j & lt; m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

आउटपुट:

Length of LCS: 5

कार्यान्वयन Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
n = len(pattern_2)
# dp will store solutions as the iteration goes on
dp = [
    [None] * (n + 1) for item in range(m + 1)
]
for i in range(m + 1):
    for j in range(n + 1):
    if i == 0 or j == 0:
    dp[i][j] = 0
elif pattern_1[i - 1] == pattern_2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

आउटपुट:

Length of LCS: 5

अतः, दोनों स्ट्रिंग्स में सबसे लंबा सामान्य उपअनुक्रम 5 लंबाई का है।

संक्षेप में, हम DP विधि में प्रत्येक कार्य की गणना केवल एक बार कर रहे हैं। पुनरावर्ती विधि में, हमारे पास ओवरलैपिंग उप-समस्याएँ हो सकती हैं।

इस डायनेमिक प्रोग्रामिंग एल्गोरिथम में, हम 2D मैट्रिक्स का उपयोग कर रहे हैं। दो स्ट्रिंग दी जाएंगी (मान लें कि दोनों की लंबाई n है)। फिर सरणी में आवश्यक स्थान nx n है। यदि स्ट्रिंग्स काफी बड़ी हैं, तो हमें DP समाधान के मेमोरी-अनुकूलित संस्करण की आवश्यकता होगी।

कोड में लिया गया सरलीकृत तर्क इस प्रकार है:

• एक 2D ऐरे DP[m][n] घोषित करें.
• DP सारणी की पहली पंक्ति और पहले कॉलम को 0 से भरें।
• पुनरावृत्ति के लिए i और j लें।
• यदि पैटर्न1[i] पैटर्न2[j] के बराबर है, तो DP[i][j] = DP[i-1][j-1] + 1 अपडेट करें
• यदि पैटर्न1[i] पैटर्न2[j] के बराबर नहीं है, तो DP[i][j], DP[i-1][j] और DP[i][j-1] के बीच का अधिकतम मान होगा।
• तब तक जारी रखें जब तक i और j, m और n तक न पहुंच जाएं।
• अंतिम तत्व या DP[m-1][n-1] में लंबाई होगी।

यहाँ, इसे DP[m-1][n-1] के रूप में संबोधित किया गया है, क्योंकि सरणी सूचकांक 0 से शुरू होता है।

सारांश

• डीपी विधि की समय जटिलता कम है; यह O(mn) है, जहां m और n इनपुट स्ट्रिंग या सारणी की लंबाई हैं।
• डीपी पुनरावर्ती दृष्टिकोण की तुलना में अधिक तेज़ दृष्टिकोण है, जिसकी समय जटिलता है ओ(एन*2^m).
• डायनेमिक प्रोग्रामिंग (DP) मेमोरी ऑप्टिमाइज़ नहीं है। हमने 2D सरणी का उपयोग किया जिसकी लंबाई m*n है। इसलिए, स्पेस जटिलता (m*n) है।
• पुनरावर्ती विधि में, सबसे खराब स्थिति में, यह अधिकतम मेमोरी m+n घेरेगी, जो मूलतः इनपुट की गई स्ट्रिंग की कुल लंबाई है।
• आज का आधुनिक कंप्यूटर इतनी मेमोरी संभालने के लिए पर्याप्त है।