मैट्रिक्स का विस्तार करने पर आधारित एक समस्या पर चर्चा करें। एक्सपैंडिंग मैट्रिक्स एक मैट्रिक्स है जिसका आकार किसी कारक द्वारा लगातार बढ़ता है।
यहां हमारे पास वर्णों का एक मैट्रिक्स है जिसका आकार 2 के कारक से बढ़ रहा है, यानी यदि मैट्रिक्स का मूल आकार N * N है, तो विस्तारित मैट्रिक्स का आकार 2N * 2N हो जाता है। हमें (i, j) पर मौजूद वर्णों का एक क्रम दिया गया है, और हमें (i, (j - N - 1)%N) पर मौजूद वर्णों का क्रम लौटाना होगा।
आइए कुछ प्रारंभिक विस्तारित मैट्रिक्स को देखकर समझते हैं,
दिया गया मैट्रिक्स -> [a, b] [c, d], 2 X 2 मैट्रिक्स
{a, b, c, d} से गुणा करना
A X [a, b] B X [a, b] C X [a, b] D X [a, b]
[c, d] [c, d] [c, d] [c, d]
विस्तारित मैट्रिक्स -> [aa, ab, ba, bb] [ac, ad, bc, bd] [ca, cb, da, db] [cc, cd, dc, dd], 4X4 मैट्रिक्स
फिर से विस्तार करने के लिए, इसे {a, b, c, d} से गुणा करें और 8X8 आकार का मैट्रिक्स बनेगा।
विस्तारित मैट्रिक्स -> [aaa, aab, aba, abb, baa, bab, bba, bbb] [aac, aad, abc, abd, bac, bad, bbc, bbd] [aca, acb, ada, adb, bca, bcb, bda, bdb] [acc, acd, adc, add, bcc, bcd, bdc, bdd] [caa, cab, cba, cbb, daa, dab, dba, dbb] [cac, cad, cbc, cbd, dac, dad, dbc, dbd] [cca, ccb, cda, cdb, dca, dcb, dda, ddb] [ccc, ccd, cdc, cdd, dcc, dcd, ddc, ddd]
यहां दो प्रारंभिक विस्तारित मैट्रिक्स हैं; तो मान लीजिए हमें वर्णों का क्रम "bcc" दिया गया है, तो हमें इसके ठीक बाएं वाले क्रम को लौटाना होगा, यानी "add"। साथ ही, मैट्रिक्स को गोलाकार माना जाता है, यानी यदि दिया गया क्रम (i, 0) पर है, तो (i, N-1) पर मौजूद क्रम को लौटाएं। उदाहरण के लिए:
इनपुट: abb आउटपुट: aba व्याख्या: 8X8 मैट्रिक्स में abb के ठीक बाएं वाला क्रम aba है। इनपुट: aadc आउटपुट: aacd इनपुट: abbcd आउटपुट: abbcc
समाधान खोजने का दृष्टिकोण
समस्या को पहली बार देखने पर और एकमात्र समाधान जो दिमाग में आता है वह है उस विस्तारित मैट्रिक्स को ढूंढना जिसमें दिया गया क्रम हो लेकिन यह बहुत जटिल नहीं लगता। हमें पहले मैट्रिक्स बनाना होगा और फिर क्रम को खोजना होगा।
कुशल दृष्टिकोण
कुछ प्रारंभिक विस्तारित मैट्रिक्स को देखने के बाद, हमें एक पैटर्न मिला जिसके माध्यम से हम पिछला तत्व देख सकते हैं। यानी:
वर्णों के क्रम को अंतिम इंडेक्स से ट्रैवर्स करें।
यदि इंडेक्स किया गया तत्व 'b' या 'd' है, तो इसे 'a' या 'c' में बदलें और एरे को ट्रैवर्स करना बंद करें।
यदि इंडेक्स किया गया तत्व 'a' या 'c' है, तो इसे 'b' या 'd' में बदलें और अगले इंडेक्स पर जाएं और उसे जांचें।
उदाहरण
उपरोक्त दृष्टिकोण के लिए C++ कोड
#include <bits/stdc++.h>
using namespace std;
int main() {
string seq = "abbcd";
int n = seq.length();
// स्ट्रिंग को अंतिम से ट्रैवर्स करें।
for (int i = n; i >= 0; i--) {
// यदि तत्व b या d है, तो उन्हें बदलें और ट्रैवर्स करना बंद करें।
if (seq[i] == 'b') {
seq[i] = 'a';
break;
}
if (seq[i] == 'd') {
seq[i] = 'c';
break;
}
// यदि तत्व a या c है, तो उन्हें बदलें और अगले तत्व पर जाएं।
if (seq[i] == 'a')
seq[i] = 'b';
else if (seq[i] == 'c')
seq[i] = 'd';
}
cout << "पिछला क्रम है: " << seq;
return 0;
}
आउटपुट
पिछला क्रम है: abbcc
निष्कर्ष
इस लेख में, हमने विस्तारित वर्ण मैट्रिक्स पर चर्चा की और यह कैसे बना। हमने एक्सपैंडिंग मैट्रिक्स में पिछला तत्व खोजने की समस्या पर भी चर्चा की। हमने मैट्रिक्स के वर्णों का विस्तार करके बनाए गए पैटर्न को समझकर इस समस्या को हल किया।
हमने इस समस्या के लिए C++ कोड पर भी चर्चा की जिसे हम C, Java, Python आदि किसी भी प्रोग्रामिंग भाषा में लिख सकते हैं। आशा है कि आपको यह ट्यूटोरियल मददगार लगा होगा।
