N-th permutation (N-তম পারমুটেশন)

figure13

পারমুটেশন (permutation) বা বিন্যাস প্রোগ্রামারদের খুব পরিচিত এক বিষয়। প্রোগ্রামিংয়ে হাতেখড়ি হবার আগেই আসলে আমাদের পারমুটেশনের সাথে পরিচয় হয়ে যায়। এজন্য পারমুটেশন কি বা পারমুটেশনের সূচনার কথা বলার আপাতত প্রয়োজন মনে করছি না। যদি কেউ পারমুটেশন বের করার সেই বিখ্যাত সূত্র ভুলে গিয়ে থাকো শুধু তাদের মনে করিয়ে দিচ্ছি।

perm

“১-৯ পর্যন্ত অংকগুলি(digit) ব্যবহার করে ৩ অংকের কতগুলি সংখ্যা বানানো যায়?”- এরকম কাগুজে সমস্যার সমাধান পরীক্ষার খাতায় ‘ধুম-ধাম’ লিখে দিয়ে আসার পর যখন একজন প্রোগ্রামার কীবোর্ড টিপে পারমুটেশন সমস্যার সমাধান করতে বসেন তখন তার সামনে প্রথম চ্যালেঞ্জই হয় ‘পারমুটেশন জেনারেট(permutation generate)’ করা। যেমন- উপরের ছবির মত করে যদি বলা হয় ‘ABC’ দিয়ে যতগুলো বিন্যাস তৈরি করা সম্ভব সবগুলি বিন্যাস তৈরি করার জন্য একটা কোড কর। তখন তো প্রোগ্রামার বগল বাজাতে বাজাতে ৩ টা লুপ মেরে দিয়ে সমস্যাটার সমাধান করে দিলেন। কিন্তু যখন ৫টা কিংবা ১০টা অংকের জন্য একই কাজ করতে বলা হবে তখন নিশ্চয়ই একইভাবে ৫টা-১০টা লুপ মেরে দিয়ে এই সমস্যার সমাধান করা যাবে না, তাই না?
কিভাবে তাহলে পারমুটেশন বের করা যায়?
পারমুটেশন বের করার সহজ ২টা বুদ্ধির কথা বলবো।
প্রথম বুদ্ধি হলো, STL এর next_permutation() এবং prev_permutation() ব্যবহার করে খুব সহজেই পারমুটেশন বের করা যায়।
আরেকটা বুদ্ধি হলো, ব্যাকট্র্যাকিং করে পারমুটেশন জেনারেট করা। এটা ভালোভাবে বুঝতে হলে এখানে দেখতে পারো।
যাই হোক, উপরের ২টা বুদ্ধিই হলো All permutation generate এর বুদ্ধি। আমি এই পোষ্টে আরেকটা বুদ্ধি নিয়ে বলবো যেটা হলো,“আগের পারমুটেশনগুলো জেনারেট না করেই N-তম পারমুটেশন কিভাবে বের করা যায়”
সবচাইতে ভালো বুদ্ধি হলো, এই পর্যন্ত পড়ার পর নীচের টুকু পড়ার আগে নিজে নিজে একটু চিন্তা করা, কাজটা আসলেই কিভাবে করা যায়? যেমন, ‘abc’ দিয়ে বলা হলো এটার 5-তম বিন্যাসটা কি হবে? আগের গুলো বের না করেই কি বলে দেয়া যায় যে 5-তম বিন্যাস হবে ‘cab’?
bright-idea1
চিন্তা করার পরও যাদের ‘মাথার উপর বাত্তি’ জ্বলে নাই তাদের জন্য নীচের অংশ। 🙂
মনে করি, উদাহরণ হিসেবে আমাদের হাতে আছে, ‘1234’. এখন বোঝার সুবিধার জন্য আমরা দেখি যে, ‘1234’ এর সবগুলি পারমুটেশন কি কি?
2013-06-27_220756
লক্ষ্যণীয় যে, আমাদের উদাহরণে 4 টা ডিজিট- ‘1’, ‘2’, ‘3’, ‘4’. আর  আমরা আমাদের মোট 4! = 24 টা বিন্যাসকে 4 ভাগে ভাগ করেছি যেখানে প্রতিভাগে (4-1)! = 3! = 6 টা করে বিন্যাস আছে।
তারমানে আমরা সাধারণভাবে বলতে পারি, 
যদি N টা ডিজিট দেয়া থাকে তাহলে তার N! বিন্যাসকে আমরা N ভাগে ভাগ করতে পারবো, যেখানে প্রতি ভাগে (N-1)! টা বিন্যাস থাকবে।
 
 এখন এই (N-1)! বিন্যাসের N টা ভাগ কি আমাদের কোনো কাজে লাগবে?
উপরের টেবিলটা দেখলেই উত্তরটা পাওয়া যাবে। দেখা যাচ্ছে, প্রথম ভাগে সবগুলো বিন্যাসের প্রথম অক্ষরটা ‘1’ তারমানে আমাদের প্রথম ডিজিট, তারপরের ভাগের প্রথম অক্ষর ‘2’ মানে আমাদের দ্বিতীয় ডিজিট, এভাবে বাকিগুলো। তারমানে হলো, মনে করি আমাদের ‘1234’ এর 17-তম বিন্যাস বের করতে বলা হয়েছে। এখন আমরা দেখবো ১৭ সংখ্যার বিন্যাসটা কত-তম ঘরে পড়বে। তাহলেই আমরা আমাদের কাঙ্খিত বিন্যাসের প্রথম অক্ষর কি হবে বলে দিতে পারবো।
তাহলে, ১৭-তম বিন্যাস কোনঘরে পড়বে আমরা বের করতে পারি, (17 / 3!) = 3 (after ceiling) . তারমানে ৩য় ঘরে। সুতরাং আমাদের উত্তরের প্রথম সংখ্যাটা হবে ‘3’.
এখন আমরা জানি যে আমাদের কাঙ্খিত বিন্যাসটি ৩য় ঘরে আছে। এবার আমরা শুধু ৩য় ঘরের দিকেই নজর দেবো আর এটাকেও আগের মত ভাগ করবো। যেহেতু আমরা প্রথম সংখ্যাটা কি হবে জেনে গেছি, তারমানে আমাদের কাজ হবে শেষের ৩ সংখ্যা ( ‘1’, ‘2’, ‘4’) নিয়ে। তাহলে আমাদের টেবিলটি হবে এরকম-
2013-06-27_223413
এখানে, মোট (N-1)! = 3! = 6 টা বিন্যাস আছে (6/(N-2)!) = 3 ভাগে, এবং প্রতিভাগে আছে (N-2)! = 2 টি বিন্যাস। আমরা যেহেতু আগের ২ ভাগে মোট 2* 3! = 12 টি বিন্যাস বাদ দিয়েছে, তারমানে এখন আমাদের 17-12 = 5 তম বিন্যাসটি খুঁজতে হবে। (এটাকে 17 mod 6 = 5 করেও পাওয়া যায়)
এখানেও আমরা দেখেবো যে, প্রতিটি ভাগে ‘২য়’ সংখ্যাটি একই। তারমানে আমরা আগের পদ্ধতিতে, 5 / 2! = 3 (after ceiling) , মানে ৩য় ঘরে আমাদের উত্তরটি পাবো।
তারমানে আমাদের ২য় সংখ্যাটি হবে ‘1’, ‘2’, ‘4’ এর মধ্যে ৩য়টি অর্থাৎ ‘4’। (যেহেতু, ‘3’ ইতোমধ্যে নেয়া হয়ে গেছে।
এখন বাকি ২টি সংখ্যার জন্য আমরা পাবো-
2013-06-27_224732
একইভাবে, হিসেব করতে থাকলে আমরা দেখবো আমাদের ৩য় সংখ্যাটি ‘1’ এবং ৪র্থ সংখ্যাটি ‘2’।
তারমানে আমাদের উত্তরটি দাঁড়ায় ‘3412’ , যেটি 17-তম বিন্যাস।
ব্যস হয়ে গেলো আমাদের N-তম বিন্যাস।
এখানে সবগুলি বিন্যাস দেখানোর কারণ হচ্ছে, সাধারণ পদ্ধতিটা বোঝানো। এখন খুব সহজেই N-তম পারমুটেশন বের করার কোড করে ফেলা যায়, উপরের বুদ্ধিতে, যেখানে বাকি বিন্যাসগুলো বের করার দরকার পড়ে না।
নাহ, আমি কোড করে দিচ্ছি না। ওটা তোমার কাজ। 🙂
আচ্ছা যদি এরকম দেয়া থাকে –
একটা পারমুটেশন ‘cba’ দেয়া আছে, এটা কততম পারমুটেশন?
তাহলে কি করবো???
একটু মাথা খাটালেই কইয়ের তেল দিয়ে কইটা ভাজা যাবে। 🙂
মানে হলো, আমরা একটু আগে যে বুদ্ধি দিয়ে N-তম পারমুটেশন বের করেছি, এখনও সেই বুদ্ধিটাকে উলটে দিয়ে আমরা একাজটা করে ফেলতে পারি।
কিভাবে???
এখানে দেখা যাচ্ছে, ১ম অক্ষর ‘c’. তার মানে আমরা বুঝতে পারছি, 3 টি সংখ্যার জন্য 3 টি ভাগে আমরা যে টেবিলটি বানাতাম (আগের বুদ্ধির প্রথম ধাপ) তার ৩য় ঘরে আছে আমাদের পারমুটেশনটি। তারমানে আগের ২ ঘরে আমাদের বিন্যাস আছে 2*(3-1)! = 4 টি।
এখন, পরের অক্ষর ‘b’ এর জন্যও আমরা বলতে পারি,  বাকি ২ অক্ষরের জন্য যে ২ ভাগে একটি টেবিল বানানো হবে তার ২য় ঘরে থাকবে ‘b’. তারমানে এর আগে একটি ঘরে 1*(3-2)! = 1 টি বিন্যাস আছে। তারমানে এখন পর্যন্ত আমরা বিন্যাস অতিক্রম করেছি (মানে বর্তমান বিন্যাসের আগে আছে)  ৪+১=৫ টি।
অবশিষ্ট অক্ষর ‘a’। এবং এটির পূর্বে আর কোন বিন্যাস নেই।
সুতরাং, আমাদের প্রদত্ত বিন্যাস ‘cba’ এর আগে বিন্যাস আছে ৪+১=৫ টি। তারমানে এটি ৬ষ্ঠ বিন্যাস।
তারমানে আমাদেরকে পারমুটেশন দেয়া হলেও আমরা খুব সহজে বলে দিতে পারবো বিন্যাসটি কততম।
পারমুটেশন নিয়ে আজকে এ পর্যন্তই।
বি:দ্র: ধরেই নিচ্ছি এ পোষ্টটির কিছুই তোমার মাথায় ঢুকেনি। সুতরাং, এখন একটা কলম নাও, আর একটা কাগজ নাও। তারপর সেখানো নিজের মত করে হিসেব করে বোঝার চেষ্টা করো, আসলেই ব্যাপারটা কি হয়? আশা করি তখন আরো সহজে বুঝতে পারবে। 🙂

Coding for life…………………………………

Want to like or share?:
0

2 comments

  1. Genius ….. ভাইয়া । ক্যারি অন । আপনারা না থাকলে আমাদের যে কি হোতো । মজার একটা জিনিস শিখলাম আপনার ” নবীন প্রোগ্রামারদের জন্য ” পোস্ট টা পড়ে । এখন কোড টা করে ৩ মাস আগের আনসলভড প্রব্লেম টা সল্ভ করা যাবে ।

Leave a Reply

Your email address will not be published. Required fields are marked *