একটি স্ট্রিংয়ের পারমুটেশন (বিন্যাস) হলো সেই স্ট্রিংয়ের ক্যারেক্টারগুলো যেকোনো ক্রমে সাজিয়ে একটি নতুন স্ট্রিং বানানো। এই টিউটোরিয়ালে আমরা আলোচনা করব কিভাবে C++-র Standard Template Library (STL) ব্যবহার করে একটি স্ট্রিংয়ের সব পারমুটেশন প্রিন্ট করা যায়। উদাহরণ −
ইনপুট: s = "ADT" আউটপুট: "ADT", "ATD", "DAT", "DTA", "TAD", "TDA" ব্যাখ্যা: আউটপুটে সব স্ট্রিং একই তিনটি ক্যারেক্টার দিয়ে বানানো হয়েছে শুধু ক্রম বদলে, তাই এগুলো স্ট্রিংয়ের পারমুটেশন। এছাড়া এগুলোই s-এর সকল সম্ভাব্য পারমুটেশন।
এক স্ট্রিংয়ের সব পারমুটেশন প্রিন্ট করার দুটি পদ্ধতি রয়েছে।
প্রথম পদ্ধতিতে STL-এর rotate ফাংশন ব্যবহার করা হবে। এই ফাংশন স্ট্রিং রোটেট (rotate) করে, এবং আমরা রিকার্সন (recursion) ব্যবহার করে পারমুটেশন প্রিন্ট করব।
উপরোক্ত পদ্ধতির C++ কোড
#include<bits/stdc++.h> using namespace std; void permutations(string s, string ans){ if(s.size() == 0) { // রোটেট করার স্ট্রিং খালি হলে পারমুটেশন ans-এ আছে cout << ans << "\n"; return; } for(int i = 0; i < s.size(); i++){ permutations(s.substr(1), ans + s[0]); // প্রথম ক্যারেক্টার ans-এ যোগ // ইনডেক্স ১ থেকে বাকি সব রোটেট স্ট্রিংয়ে পাস rotate(s.begin(), s.begin()+1, s.end()); // রোটেট করে দ্বিতীয় ক্যারেক্টারকে প্রথমে আনা } } int main(){ string s = "ADT"; // দেওয়া স্ট্রিং permutations(s, ""); return 0; }
ADT ATD DTA DAT TAD TDA
এখন STL-এর অন্য একটি ফাংশন next_permutation ব্যবহার করব। নাম অনুযায়ী, এই ফাংশন বতায় স্ট্রিংয়ের পরবর্তী পারমুটেশন আছে কিনা। নেই তবে false রিটার্ন করে।
যেহেতু এই ফাংশন পরবর্তী পারমুটেশন চেক করে, তাই প্রথমে স্ট্রিংটি লেক্সিকোগ্রাফিক্যালি (lexicographically) সর্ট করতে হবে যাতে সব সম্ভাব্য পারমুটেশন পাওয়া যায়।
উপরোক্ত পদ্ধতির C++ কোড
#include<bits/stdc++.h> using namespace std; int main(){ string s = "ADT"; // দেওয়া স্ট্রিং sort(s.begin(), s.end()); // স্ট্রিং সর্ট করা do{ cout << s << "\n"; // পারমুটেশন প্রিন্ট } while(next_permutation(s.begin(), s.end())); // next_permutation false রিটার্ন না করতেই চলবে return 0; }
ADT ATD DAT DTA TAD TDA
উপরোক্ত প্রোগ্রামে, আমরা স্ট্রিংটি সর্ট করেছি এবং next_permutation ফাংশন দিয়ে সব সম্ভাব্য পারমুটেশন প্রিন্ট করেছি।
এই টিউটোরিয়ালে আমরা C++-র STL সাহায্যে একটি স্ট্রিংয়ের সব সম্ভাব্য পারমুটেশন প্রিন্ট করেছি। আমরা এই সমস্যার C++ প্রোগ্রাম এবং কিছু গুরুত্বপূর্ণ STL ফাংশন ও তাদের ব্যবহার দেখেছি। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।