প্রথমেই সাবসেট ও সাবসিকোয়েন্স নিয়ে আলোচনা করা প্রয়োজন। এই দুটিকে অনেক বেশি গুলিয়ে ফেলা হয়।
অনেক প্রবলেম সেটারগণ ও তাদের প্রবলেমে হয়ত সাবসিকোয়েন্স নিয়ে কাজ করার জন্য বলেছেন কিন্তু প্রবলেমে লিখে দিয়েছেন সাবসেট। প্রথমেই দেখা যাক সাবসেট নিয়ে। সাবসেট হচ্ছে একটি সেট থেকে পাশাপাশি কিছু ক্যারেক্টার নিয়ে আরেকটি সেট বানালে সেটি হচ্ছে প্রথম সেটটির সাবসেট। ধরি, "abcd" একটি সেট। এখন এখানে থেকে আমি যদি "bc" "abc" "b" ইত্যাদি নিয়ে আলাদা আলাদা সেট বানাই তাহলে এগুলো হচ্ছে "abcd" এর সাবসেট। কিন্তু, "bd" "abd" "cb" ইত্যাদি "abcd" এর সাবসেট নয়। পুরো সেট টিও কিন্তু সাবসেট হতে পারে আবার ফাঁকা সেট ও সাবসেট হতে পারে।
একটি সেট থেকে ক্যারেক্টারগুলোর পর্যায়ক্রম ঠিক রেখে কিছু ক্যারেক্টার নিয়ে আরেকটি সেট বানালে সেটি হচ্ছে প্রথম সেটটির সাবসিকোয়েন্স। "abcde" যদি একটি সেট হয়ে তাহলে "bcd" "bde" "abde" "ae" ইত্যাদি সেট বা সিকোয়েন্সগুলো হচ্ছে "abcde" এর সাবসিকোয়েন্স। কিন্তু্, "dbc" "ea" ইত্যাদি "abcde" এর সাবসিকোয়েন্স নয়। কারণ, এদের পর্যায়ক্রম ঠিক নেই। সাবসেটের মত পুরো সেট টিও সাবসিকোয়েন্স হতে পারে এবং ফাঁকা সেট ও সাবসিকোয়েন্স হতে পারে।
তাহলে বলা যায়, সব সাবসেটকেই সাবসিকোয়েন্স বলা যায় কিন্তু সব সাবসিকোয়েন্স কে সাবসেট বলা যায় না।
এখন দেখব কীভাবে একটি সেট থেকে সবরকম সাবসিকোয়েন্স বের করতে হয়। "abc" কে যদি একটি সেট ধরি। তাহলে, "a" "b" "c" "ab" "ac" "bc" "abc" এবং ফাঁকা সিকোয়েন্স টি সহ মোট আঁটটি সাবসিকোয়েন্স পাওয়া যাবে। এভাবে 3 টি ক্যারেক্টারের জন্য 8 টি, 4 টি ক্যারেক্টারের জন্য 16 টি, 5 টি ক্যারেক্টারের জন্য 32 টি সাবসিকোয়েন্স পাওয়া যাবে। মানে n টি সাবসিকোয়েন্সের জন্য 2ⁿ টি সাবসিকোয়েন্স পাওয়া যাবে। এখন 0 থেকে 2ⁿ-1 পর্যন্ত সংখ্যাগুলোকে যদি বাইনারিতে উপস্থাপন করে সাজাই, যেমন, 0 থেকে 7 (n=3) পর্যন্ত সংখ্যাগুলো থেকে 5 কে বাইনারিতে উপস্থাপন করলে হবে 101 এবং যে বিটে 1 আছে সেট থেকে সেই পজিশনের ক্যারেক্টার নিয়ে আরেকটি সেট বানালে সেটি কিন্তু একটি সাবসিকোয়েন্স হয়ে যাচ্ছে।
"abc"
101
"a c"
বা, "ac" একটি সাবসিকোয়েন্স হয়ে যাচ্ছে। "abc" এর জন্য সবগুলো সংখ্যার জন্য সাজিয়ে দেখতে পারি তাহলে বিষয়টি আরো পরিস্কার হয়ে যাবে আশাকরি।
0 000 { , , } // ফাঁকা সিকোয়েন্স
1 001 {a, , } // "a"
2 010 { ,b, } // "b"
3 011 {a,b, } // "ab"
4 100 { , ,c} // "c"
5 101 {a, , c} // "ac"
6 110 { ,b,c} // "bc"
7 111 {a,b,c} // "abc"
এখন কোন একটি সংখ্যার একটি বিট 1 নাকি 0 তা দেখব কীভাবে? অবশ্যই & অপারেটরের সাহায্য নিতে হবে আর এমন একটি সংখ্যা দিয়ে & করতে হবে যেন যত তম বিট টি পরীক্ষা করব সেই বিটেই শুধু 1 থাকবে পরীক্ষা করার জন্য নেওয়া সংখ্যাটিতে।
যদি 5 এর দ্বিতীয় বিট দেখতে চাই 0 নাকি 1 তাহলে নিতে হবে 2
5 101
2 010
যদি 5 এর প্রথম বিট দেখতে চাই তাহলে নিতে হবে 1
5 101
1 001
যদি 5 এর তৃতীয় বিট দেখতে চাই তাহলে নিতে হবে 4
5 101
4 100
বুঝা যাচ্ছে 2 এর পাওয়ার নিয়ে পরীক্ষা করতে হবে 1 2 4 8 16 ইত্যাদি। এর কারণ & অপারেটর শুধু দুইপাশে 1 থাকলেই 1 রিটার্ন করে তাই কোন বিট যদি 1 হয় তাহলে & অপারেটর পরীক্ষা করার জন্য যে সংখ্যা নিয়েছি সেটিই রিটার্ন করবে আর 0 হলে শুধু 0 ই রিটার্ন করবে।
5 101
2 010
--------
0 000
আবার তৃতীয় বিট দেখতে চাইলে,
5 101
4 100
--------
4 100
এভাবে সহজেই একটি সংখ্যার কোন বিট 0 নাকি 1 তা পরীক্ষা করতে পারব। এখন তাহলে কাজ হচ্ছে ইনপুট নেওয়া স্ট্রিং বা অ্যারে সাইজ থেকে বের করতে হবে কতটি সাবসিকোয়েন্স বের করতে হবে, int len = (1<<n); এখানে, n হচ্ছে অ্যারে/স্ট্রিং টির সাইজ। এখন 0 থেকে len-1 পর্যন্ত সংখ্যাগুলোর বিট পরীক্ষা করে সাবসিকোয়েন্স বের করে ফেলতে হবে। আমার মনে হয়ে একটু বিস্তারিতই ব্যাখ্যা করেছি বিষয়টি। তাই আশা করছি নিচের কোড দেখার আগেই অনেকেই সবরকম সাবসিকোয়েন্স বের করার প্রোগ্রামটি করে ফেলতে পারবে।
|
#include <bits/stdc++.h>
using namespace std;
bool check(int n, int pos) { // function to check the j-th bit
if ((n & (1<<pos)) > 0)return true;
else return false;
}
void all_possible_subsequence(string s) {
int n = s.size();
int len = (1<<n); // len is now 2 to the power of n
for (int i = 0;i < len;i++) {
string sub;
for (int j = 0;j < n;j++) {
if (check(i, j) == true){ // checking j-th bit is 0 or 1
sub += s[j]; // insert the j-th char to sub
}
}
cout << sub << '\n'; // printing current subsequence
}
}
int main()
{
string str = “abc”;
all_possible_subsequence(str);
return 0;
}
|
এখন আসা যাক এর কমপ্লেক্সিটি নিয়ে। যেহেতু, 2ⁿ টি সাবসিকোয়েন্স তাই 2ⁿ পর্যন্ত আমাকে লুপ চালাতে হবেই এবং প্রতিবার আবার n পর্যন্ত লুপ চালিয়ে সাবসিকোয়েন্স বের করতে হবে। তাহলে এর কমপ্লেক্সিটি বলা যায় O(2ⁿ * n)।
No comments