ইটারেটিভ পদ্ধতিতে স্ট্রিংয়ের সব পারমুটেশন জেনারেট করা

এই অনুচ্ছেদে আমরা দেখব কীভাবে একটি স্ট্রিংয়ের সব পারমুটেশন জেনারেট করা যায়। রিকার্সিভ পদ্ধতি খুব সহজ। এটি ব্যাকট্র্যাকিং প্রসিডিউর ব্যবহার করে। কিন্তু এখানে আমরা ইটারেটিভ পদ্ধতি ব্যবহার করব।

স্ট্রিং ABC-এর সব পারমুটেশন হলো {ABC, ACB, BAC, BCA, CAB, CBA}। ভালো ধারণার জন্য অ্যালগরিদমটি দেখি।

অ্যালগরিদম

getAllPerm(str)

begin sort the characters of the string while true, do print the string str i := length of str − 1 while str[i - 1] >= str[i], do i := i − 1 if i is 0, then return end if done j := length of str − 1 while j > i AND str[j] <= str[i − 1], do j := j − 1 done exchange the characters from position str[i - 1], str[j] reverse the string. done end

উদাহরণ

#include  #include  using namespace std; void getAllPerm(string str){ sort(str.begin(), str.end()); while (true){ cout << str << endl; int i = str.length() - 1; while (str[i-1] >= str[i]){ if (--i == 0) return; } int j = str.length() - 1; while (j > i && str[j] <= str[i - 1]) j--; swap(str[i - 1], str[j]); reverse (str.begin() + i, str.end()); } } int main(){ string str = "WXYZ"; getAllPerm(str); }

আউটপুট

WXYZ WXZY WYXZ WYZX WZXY WZYX XWYZ XWZY XYWZ XYZW XZWY XZYW YWXZ YWZX YXWZ YXZW YZWX YZXW ZWXY ZWYX ZXWY ZXYW ZYWX ZYXW