ফ্লয়েডস সাইকেল ডিটেকশন (Floyd's Cycle Detection)
ধরুন একটা গোল রানিং ট্র্যাকে দুজন মানুষ দৌড়াচ্ছে। একজন স্বাভাবিক স্পিডে দৌড়ায়, আর অন্যজন তার ডাবল স্পিডে দৌড়ায়। তারা যদি একসাথে দৌড়ানো শুরু করে, তাহলে ফাস্ট বা দ্রুতগামীর দৌড়বিদ কি কখনো পুরো এক চক্কর ঘুরে এসে আবার ওই স্লো বা ধীরগতির দৌড়বিদকে ধরতে পারবে? উত্তর হলো হ্যাঁ — সে অবশ্যই পারবে, এবং খুব তাড়াতাড়িই ধরে ফেলবে।
এবার কল্পনা করুন, ওই রানিং ট্র্যাকটা হলো একটা লিংকড লিস্ট, যার ভেতরে একটা সাইকেল বা লুপ আছে (অর্থাৎ লিস্টের শেষ মাথাটা আবার পেছনের দিকের কোনো একটা নোডের সাথে জোড়া লাগানো)। আমরা একটা স্লো পয়েন্টার (Slow pointer) নিলাম, যে প্রতি ধাপে এক ঘর করে এগোয়। আর একটা ফাস্ট পয়েন্টার (Fast pointer) নিলাম, যে এক লাফে দুই ঘর করে এগোয়। যদি ওই লিস্টের মধ্যে সত্যি কোনো লুপ থাকে, তবে ফাস্ট পয়েন্টারটা ঘুরতে ঘুরতে ঠিকই একসময় স্লো পয়েন্টারকে পেছন থেকে এসে ধরে ফেলবে এবং দুজনে একই নোডে এসে দাঁড়াবে। আর যদি কোনো লুপ না থাকে, তবে ফাস্ট পয়েন্টার সবার আগে লিস্টের শেষ মাথায় (null-এ) গিয়ে পৌঁছে যাবে।
এই চমৎকার বুদ্ধির নামই হলো ফ্লয়েডস সাইকেল ডিটেকশন অ্যালগরিদম (Floyd's Cycle Detection Algorithm) — যাকে আদর করে অনেকেই কচ্ছপ ও খরগোশ (tortoise and the hare) অ্যালগরিদম বলে। এটা এমন একটা সমস্যা, যা সমাধান করতে অন্যান্য নিয়মে অনেক মেমোরি লাগে, কিন্তু এই অ্যালগরিদমটা O(1) স্পেস বা মেমোরিতে কাজটা করে ফেলে! কোনো হ্যাশ সেট লাগে না, কোন কোন নোডে গেছি তার হিসাব রাখতে হয় না—শুধু দুটো সাধাসিধা পয়েন্টার দিয়ে কেল্লাফতে।
← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন
প্রথম ধাপ: আদৌ কি কোনো সাইকেল বা লুপ আছে?
এটা কাজ করে কেন? যদি লুপের সাইজ k হয়, তবে ফাস্ট পয়েন্টার যখন লুপের ভেতরে ঢোকে, তখন সে প্রতি ধাপে স্লো পয়েন্টারের চেয়ে ১ ঘর করে এগিয়ে যায় (বা দূরত্ব কমায়)। তাই দুজনে লুপের ভেতরে ঢোকার পর সর্বোচ্চ k টা স্টেপের মধ্যেই তারা একে অপরের সাথে ধাক্কা খাবে বা মিলবে। মোট সময় লাগে: O(n)।
দ্বিতীয় ধাপ: সাইকেল বা লুপটা ঠিক কোন নোড থেকে শুরু হয়েছে?
একবার যখন আপনি ধরে ফেললেন যে লুপ আছে এবং তারা একটা নোডে গিয়ে মিলেছে, এরপর লুপটা ঠিক কোন নোড থেকে শুরু হয়েছে, সেটা বের করার জন্য দারুণ একটা ম্যাথমেটিক্যাল ট্রিক আছে:
- দুজনের যেখানে দেখা হয়েছিল (meeting point), একটা পয়েন্টারকে ঠিক সেখানেই দাঁড় করিয়ে রাখুন।
- অন্য পয়েন্টারটাকে একদম শুরুতে (
head-এ) পাঠিয়ে দিন। - এবার দুজনকেই সমান স্পিডে, অর্থাৎ এক ধাপ করে করে সামনে এগোন।
- তারা আবার যে নোডে গিয়ে মিলবে বা ধাক্কা খাবে, ঠিক সেটাই হলো সাইকেল বা লুপ শুরু হওয়ার জায়গা!
কিন্তু কেন? এর পেছনে একটা সুন্দর অঙ্ক আছে। ধরুন লিস্টের শুরু থেকে লুপের শুরু পর্যন্ত দূরত্ব হলো F, আর লুপের শুরু থেকে যেখানে তাদের প্রথমবার দেখা হয়েছিল সেই দূরত্ব হলো a। আর ধরি পুরো লুপটার সাইজ C। প্রথমবার দেখা হওয়ার সময়, স্লো পয়েন্টার হেঁটেছে F + a পথ। আর ফাস্ট পয়েন্টার যেহেতু ডাবল স্পিডে হেঁটেছে, সে হয়তো লুপের ভেতরে আরও কয়েক চক্কর (ধরি n চক্কর) বেশি দিয়েছে, তাই সে হেঁটেছে F + a + nC পথ। শর্ত অনুযায়ী: 2(F + a) = F + a + nC। এটা কাটাকাটি করলে দাঁড়ায়: F = nC − a। এর মানে হলো, যে জায়গাটায় তাদের দেখা হয়েছিল, সেখান থেকে যদি কেউ এক ধাপ করে যায়, তবে লুপের বাকি অংশ পার হয়ে আবার লুপের শুরুতে আসতে ঠিক F সংখ্যক স্টেপই লাগবে। আর ওই একই সময়ে শুরু (head) থেকে যে লোকটা আসছিল, সেও ঠিক F স্টেপ দিয়ে লুপের শুরুতে পৌঁছে যাবে। তাই দুজনে নিশ্চিতভাবে ওই লুপের শুরুতেই মিলিত হবে!
হ্যাশ সেট (Hash set) কেন ব্যবহার করবো না?
লুপ খোঁজার জন্য আমরা চাইলে একটা হ্যাশ সেট নিতে পারতাম। কোন কোন নোডে আমরা পা দিয়েছি, সবগুলোকে ওই সেটে সেভ করে রাখতে পারতাম। তারপর যখন কোনো নোডে গিয়ে দেখতাম যে "আরে, এই নোডটা তো সেটে আগে থেকেই আছে!" — তখন বুঝতাম যে লুপ আছে। এটা কাজ করে ঠিকই, কিন্তু এর জন্য মাথাপিছু O(n) বাড়তি জায়গা বা মেমোরি খরচ করতে হয়। অথচ ফ্লয়েডের অ্যালগরিদম ঠিক একই কাজটা মাত্র দুটো পয়েন্টার দিয়ে O(1) স্পেস বা মেমোরিতে করে ফেলে। বিশাল বড় কোনো লিস্ট হলে, মেমোরি বাঁচানোর এই ট্রিকটা মারাত্মক পার্থক্য গড়ে দেয়।
কোথায় কোথায় এই অ্যালগরিদম কাজে লাগে?
- ইন্টারভিউয়ের কমন সমস্যা — লিটকোডের ১৪১ (লুপ আছে কি না) এবং ১৪২ (লুপ কোথা থেকে শুরু হয়েছে) নম্বর প্রবলেম দুটো সরাসরি এই অ্যালগরিদম দিয়েই সলভ করতে হয়।
- ইনফিনিট লুপ ধরা — কাস্টম ইটারেটর বা জেনারেটরের ভেতরে কোনো ইনফিনিট লুপ আছে কি না ধরতে এটা কাজে লাগে।
- ডুপ্লিকেট সংখ্যা খোঁজা — লিটকোডের ২৮৭ নম্বর প্রবলেমটা খুব ট্রিকি। ওখানে একটা সাধারণ নম্বর অ্যারেকে লিংকড লিস্ট হিসেবে কল্পনা করে এই ফ্লয়েডের অ্যালগরিদম চালিয়ে O(n) টাইমে এবং স্পেস O(1) রেখে ডুপ্লিকেট সংখ্যা বের করতে বলা হয়।
- অঙ্কের ফ্যাক্টরাইজেশন — বড় সংখ্যার উৎপাদক বের করার পোলার্ডস রো (Pollard's rho) অ্যালগরিদমেও এই একই লুপ খোঁজার বুদ্ধি ব্যবহার করা হয়।