ব্যাকট্র্যাকিং দিয়ে সবরকম সাবসিকোয়েন্স বিন্যাস(Generate All Possible Subsuquence with Backtracking)

আগের পর্বে দেখেছিলাম কীভাবে বিটমাস্ক দিয়ে সবরকম সাবসিকোয়েন্স বের করতে হয়। এই পর্বে দেখব ব্যাকট্র্যাকিং দিয়ে। 

এই পর্ব শুরুর আগে রিকার্শন সম্পর্কে ভালো ধারণা থাকতে হবে। ব্যাকট্র্যাকিংয়ের সাথে ডায়নামিক প্রোগ্রামিংয়ের ও একটু সম্পর্ক আছে। এসব নাম শুনেই কঠিন ভাবার কিছু নেই। আসলে রিকার্শন ভালো পারলে বিষয়টা অনেক সহজ। আর ব্যাকট্র্যাকিং নিয়ে ইতিমধ্যেই বাংলায় শাফায়েত ভাইয়ের অসাধারণ এই লেখাটি থাকতে আমি আর নতুন করে বিস্তারিত আলোচনায় যাব না। তবে, অল্প কিছু আলোচনা করার চেষ্টা করব যেন বিষয়টি বুঝতে আরো একটু সুবিধা হয়। তাহলে প্রথমেই দেখা যাক ব্যাকট্র্যাকিং নিয়ে।

ব্যাকট্র্যাকিং হচ্ছে একটি টেকনিক যা দিয়ে সম্ভাব্য সবরকম উত্তর বের করে দেখা যায়। মানে নির্দিষ্ট একটি সমস্যার কতরকম উত্তর হতে পারে তার সবগুলোই বের করে দেখা। একে বলা হয় ব্রুট ফোর্স টেকনিক। এখন যদি বলি "ABC" কে কতভাবে সাজানো যাবে তিন সাইজের সেট হিসেবে? এবং একই পজিশন বারবার নেওয়া যাবে।
"AAA"
"AAB"
"AAC"
...........
...........
"CCC"
এখন যদি ট্রি হিসেবে সাজিয়ে দেখি, তাহলে ট্রি টি হবে নিচের ছবির মত। আর যেহেতু তিনটি ক্যারেক্টার থেকে তিন সাইজের সবরকম সেট দেখতে চাচ্ছি তাই মোট সেট হবে 3³ = 27 টি সেট।

ছবিটিতে দেখতে পারছি প্রথমে A তে গিয়ে আবার A তে যাচ্ছে এবং পরে আবার A যাচ্ছে। এরপরে আর যাবে না কারণ আমি বলেছি তিন সাইজের সেট বানাব এবং তিন সাইজের সেট একটি হয়ে গেছে। এরপর তৃতীয় A থেকে দ্বিতীয় A তে ফিরে যাবে বা ব্যাক করবে এবং তারপর B তে যাবে। আবার তিন সাইজের আরেকটি সেট হয়ে গেছে এবং এখন ব্যাক করে আবার C তে যাবে এবং আরেকটি সেট। এখন একেবারে প্রথম A তে ব্যাক করবে এবং তারপরে B তে যাবে। এভাবে চলতে থাকবে এবং সবগুলো সেট বের করে ফেলবে। এখন একটা রিকারসিভ ফাংশন লিখে ফেলতে পারি যেটি সবরকম সেট বের করে দিবে।

void make_all(int id, string s, string sub) {   if (id == 3) {     cout << sub << '\n';     return;   }   for (int i = 0;i < s.size();i++) {     sub += s[i];     make_all(id+1, s, sub);     sub.erase(sub.begin() + sub.size() - 1);   } }

এখানে id মানে বর্তমানে আমি কোন পজিশনে আছি সেটি নির্দেশ করছে এবং আমার বর্তমান সেট টির সাইজ কত সেটিও বলে দিতে পারছে। আর ফিরে যাওয়ার সময় sub এর শেষ ক্যারেক্টার ডিলেট করে দিচ্ছি নাহলে সেটি রয়েই যাবে। 

এখন শর্ত দেওয়া হলো একই পজিশন বারবার ব্যবহার না করে কতটি সেট পাওয়া যাবে? এখন কি আমরা সবগুলো সেট বের করে প্রতিটা সেট পরীক্ষা করে দেখব যে কোনটাতে একই পজিশন বারবার আসছে কিনা? এখন এভাবে করা কিন্তু সময়ের অনেক অপচয়। যেহেতু, আমাদের সবগুলো সেট লাগছে না। উপরের ছবির নীল দাগ দেওয়া পথে যে ক্যারেক্টারগুলো আসছে সেগুলো দিয়েই কিন্তু আমার কাঙ্ক্ষিত একেকটি সেট পাওয়া যাবে। মানে এই লাইন গুলোতেই শুধু একই পজিশন বারবার আসছে না। তাহলে, "আমার ফাংশনকে বাকিগুলোতে যেন যেতে না হয়" এমন একটি ব্যবস্থা যদি করতে পারি তাহলে কিন্তু অনেক কাজ কমে যাচ্ছে। আর এই কাজটি করার জন্যেই উপস্থিত হবেন মহামান্য ডায়নামিক প্রোগ্রামিং। এখন আমাদের কমপ্লেক্সিটি 3³ থেকে কমে গিয়ে হবে 3! বা, n! (n হচ্ছে ইনপুট অ্যারে বা স্ট্রিংয়ের সাইজ)। এখন তাহলে কাজটি কীভাবে হবে? একই পজিশনে যেন বারবার না যেতে হয় তাই আমরা একটি পজিশনে যাওয়ার পরে তা মার্ক করে রাখব এবং ফেরত আসার সময় তা আবার আনমার্ক করে রাখব। নাহলে পরের সেট তৈরিতে সমস্যা করবে। এই যে একই অতিরিক্ত কাজ যেন বারবার না হয় এটা এড়িয়ে যাওয়ার জন্য যা করলাম তাই ডায়নামিক প্রোগ্রামিং। আর এই বিষয় গুলো নিয়ে শাফায়েত ভাই তার লেখায় খুব সুন্দর করে আলোচনা করেছেন। 

এখন আসি আমাদের এই লেখার মূল বিষয় সাবসিকোয়েন্স নিয়ে। সাবসিকোয়েন্স কি সেটি আগের পর্বে বলেছি তাই এই পর্বে আর বলছি না। এখন, {1, 2, 3, 4} সবগুলো সাবসিকোয়েন্স যদি বের করি তাহলে সেগুলো হবে। 

{ }
{1}

{1 2}

{1 2 3}

{1 2 3 4}

{1 2 4}

{1 3}

{1 3 4}

{1 4}

{2}

{2 3}

{2 3 4}

{2 4}

{3}

{3 4}

{4}

এখন কমপ্লেক্সিটি আরো কম 2ⁿ। আচ্ছা আগের ফাংশনে আমরা কি করেছিলাম? প্রতি id তম পজিশনে গিয়ে সম্পূর্ণ সেট টিকে আবার কল করেছিলাম। যেহেতু সাবসিকোয়েন্সের নিয়ম অনুযায়ী বর্তমান পজিশনের পেছনে ফেলে আসা পজিশন এর সামনে বসতে পারবে না তাই প্রতি id পজিশন থেকেই 0 থেকে n-1 পর্যন্ত ক্যারেক্টারগুলো এক এক করে না পাঠিয়ে id+1 থেকে n-1 পর্যন্ত পজিশনের ক্যারেক্টারগুলো এক এক করে পাঠিয়ে দিলে খুব সহজেই হয়ে যাবে। {1, 2, 3, 4} সেট থেকে যদি ট্রি আঁকি তাহলে ট্রি টি হবে নিচের ছবির মত।

উপরে সাবসিকোয়েন্স গুলো বের করেছি তা এই ট্রি থেকেই মিলিয়ে একই অর্ডারে। আর উপরে যেভাবে বলেছি ট্রি টি আসলে সেভাবেই এঁকেছি। যেমন দ্বিতীয় পজিশনে থাকলে ফাংশনে যথাক্রমে তৃতীয় ও চতুর্থ পজিশন কে পাঠিয়ে দিয়েছি। এখন কিন্তু মার্ক করা ছাড়াই অতিরিক্ত কাজগুলো এড়িয়ে যাচ্ছি। সুতরাং এখানে ডায়নামিক প্রোগ্রামিং লাগছে না। আরেকটি বিষয় ফাংশন টি কোন বেইজ কেস ছাড়াই বন্ধ/শেষ হয়ে যাবে। এর কারণ টি বুঝতে পারলে তাহলে এই ফাংশন টি যে বুঝতে পেরেছি তা তে কোন সন্দেহ থাকে না। আশা করছি কোড দেখার আগেই নিজে একবার চেষ্টা করে দেখব। কারণ কাজটি কিন্তু খুব সহজ। 

#include <bits/stdc++.h> using namespace std; void make(int id, vector <int> ar, vector <int> sub) {   cout << "{ ";   for (int i = 0;i < sub.size();i++) {     cout << sub[i] << ' ';   }   cout << "}" << '\n';   for (int i = id;i < ar.size();i++) {     sub.push_back(ar[i]);     make(i+1, ar, sub);     sub.pop_back();   }   return; } int main() {   vector <int> ar, sub;   ar.push_back(1);   ar.push_back(2);   ar.push_back(3);   ar.push_back(4);   make(0, ar, sub);   return 0; }

অ্যারে প্রিন্ট করতে আমাকে প্রতিটি সাবসিকোয়েন্স বের করার পর আবার প্রতিটা সাবসিকোয়েন্সের প্রতিটি এলিমেন্ট একটি একটি  করে প্রিন্ট করতে হচ্ছে তাই কমপ্লেক্সিটি আগের মতই র‍য়ে যাচ্ছে। কিন্তু স্ট্রিং নিয়ে কাজ করলে কিন্তু স্ট্রিং প্রিন্ট করতে প্রতিটি ক্যারেক্টার একটি একটি করে প্রিন্ট করার প্রয়োজন নেই। তাহলে কি সময় কিছুটা কম লাগবে? 

এই বিষয়ে আরো টিউটোরিয়াল।
টিউটোরিয়াল ১