ফিশার-ইয়েটস শাফল অ্যালগরिदম (Fisher-Yates shuffle algorithm)
এই অ্যালগরিদমটি অ্যারেয়ের এলিমেন্টগুলো শাফল (shuffle) করার জন্য। অ্যারে শাফল করার জন্য নিজস্ব লজিক লিখা যায়, কিন্তু অনেক ডেভেলপার মনে করে ফিশার-ইয়েটস মডার্ন শাফল অ্যালগরিদমই অ্যারে শাফল করার সেরা পদ্ধতি। এই অ্যালগরিদমের ধাপগুলো নিচে:
অনুসরণ করার ধাপগুলো
- এই অ্যালগরিদম অনুযায়ী অ্যারেকে পিছন থেকে সামনে লুপ করা উচিত। উদাহরণস্বরূপ, ৮টি এলিমেন্ট (A,B,C,D,E,F,G,H) থাকলে ইনডেক্স ০ থেকে ৭। প্রথম লুপ পাস শেষ ইনডেক্স ৭ অর্থাৎ H-কে প্রভাবিত করবে।
- পরবর্তী ধাপ: সিলেক্টেড ইনডেক্স ৭ এবং ইনডেক্স ০-এর মধ্যে একটি র্যান্ডম নম্বর (র্যান্ডম ইনডেক্স) জেনারেট করা। ধরি র্যান্ডম ইনডেক্স ৩।
- র্যান্ডম ইনডেক্স পাওয়ার পর সিলেক্টেড ইনডেক্স এবং র্যান্ডম ইনডেক্স-এ থাকা এলিমেন্টগুলো স왪 (swap) করা। প্রদত্ত অ্যারেতে র্যান্ডম ইনডেক্সে D আছে। স왪 করার পর অ্যারে হবে A,B,C,H,E,G,F,D।
- দ্বিতীয় লুপ পাসে শেষ ইনডেক্স বাদ দিয়ে (কারণ সেটি ইতিমধ্যে লুপড) ইনডেক্স ০ এবং ৬ (A এবং F) এর মধ্যে র্যান্ডম ইনডেক্স খুঁজা। ধরি জেনারেটেড র্যান্ডম ইনডেক্স ২।
- র্যান্ডম ইনডেক্স পাওয়ার পর ইনডেক্স ৬ এবং ২-এ থাকা এলিমেন্ট স왪 করা। এখন অ্যারে দেখাবে A,B,F,H,E,G,C,D।
- এই অ্যালগরিদম একই প্যাটার্ন অনুসরণ করে: ইনডেক্স ৬ বাদ দিয়ে ইনডেক্স ৫ এবং ০-এর মধ্যে র্যান্ডম ইনডেক্স খুঁজে, এভাবে ইনডেক্স ১ পর্যন্ত চলতে থাকে। ইনডেক্স ০ লুপ করা যায় না কারণ স왪 করার জন্য ০-এর নিচে কোনো ইনডেক্স নেই।
- নোট করুন: জেনারেটেড র্যান্ডম ইনডেক্স সিলেক্টেড লুপ ইনডেক্সের সমান হতে পারে। উদাহরণস্বরূপ, লুপ চলছে ইনডেক্স ৪ এবং ০-এর মধ্যে। জেনারেটেড র্যান্ডম ইনডেক্স ৪ হলে ইনডেক্স ৪-এর মান একই পজিশনে থাকবে।
নিচের উদাহরণ ফিশার-ইয়েটস মডার্ন শাফল অ্যালগরিদম ইলাস্ট্রেট করে:
উদাহরণ
<html> <body> <script> var arr = ['A','B','C','D','E','F','G','H'] var i = arr.length, k , temp; // k is to generate random index and temp is to swap the values while(--i > 0){ k = Math.floor(Math.random() * (i+1)); temp = arr[k]; arr[k] = arr[i]; arr[i] = temp; } document.write(arr); </script> </body> </html>
আউটপুট
C,F,H,D,A,G,E,B // note that output will change for every iteration.
