ফিশার-ইয়েটস শাফেল অ্যালগরিদম
এই অ্যালগরিদম হল একটি অ্যারের উপাদানগুলিকে শাফেল করা। একটি অ্যারের উপাদানগুলিকে এলোমেলো করতে আমরা আমাদের নিজস্ব যুক্তি লিখতে পারি, কিন্তু অনেক বিকাশকারী মনে করেন যে F ইশার-ইয়েটস আধুনিক শাফেল অ্যালগরিদম একটি অ্যারের উপাদানগুলিকে শাফেল করার সর্বোত্তম উপায়। এই অ্যালগরিদমের নিম্নলিখিত ধাপ রয়েছে৷
অনুসরণ করার পদক্ষেপগুলি
- এই অ্যালগরিদম অনুসারে আমাদের অ্যারেটিকে পিছনে থেকে সামনে লুপ করা উচিত। উদাহরণস্বরূপ, নিম্নলিখিত উদাহরণে, আমাদের কাছে সূচক 0 থেকে সূচক 7 পর্যন্ত 8টি উপাদান (A,B,C,D,E,F,G,H) সমন্বিত একটি অ্যারে রয়েছে। সুতরাং প্রথম লুপ পাসটি উপাদানটিকে প্রভাবিত করবে শেষ সূচক 7 যেটি হল H.
- পরবর্তী ধাপ হল নির্বাচিত সূচক 7 এবং সূচক 0 এর মধ্যে একটি এলোমেলো সংখ্যা (এলোমেলো সূচক) তৈরি করা। ধরা যাক র্যান্ডম সূচকটি 3।
- এলোমেলো সূচক পাওয়ার পর নির্বাচিত সূচীতে এবং এলোমেলো সূচকে থাকা উপাদানগুলিকে অদলবদল করুন৷ প্রদত্ত অ্যারের র্যান্ডম সূচকের উপাদানটি হল D৷ তাই অদলবদল করার পরে, অ্যারেটি A, B, C তে পরিবর্তিত হবে ,H,E,G,F,D.
- দ্বিতীয় লুপ পাসে শুধু শেষ সূচকটিকে উপেক্ষা করুন (যেহেতু এটি ইতিমধ্যেই লুপ করা হয়েছে) এবং সূচক 0 এবং সূচক 6 এর মধ্যে এলোমেলো সূচকটি খুঁজে বের করার চেষ্টা করুন যা A এবং F উপাদানগুলির মধ্যে রয়েছে। জেনারেট হওয়া র্যান্ডম সূচকটি 2 হতে দিন।
- এলোমেলো সূচক পাওয়ার পরে আসুন 6 এবং 2-এ সূচীতে উপাদানগুলিকে অদলবদল করি। এখন অ্যারেটি A,B,F,H,E,G,C,D হিসাবে দেখাবে।
- এই অ্যালগরিদমটি একই প্যাটার্ন অনুসরণ করে যে এটি সূচক 6 উপেক্ষা করে এবং সূচক 5 এবং সূচক 0 এর মধ্যে এলোমেলো সূচী খুঁজে পেতে শুরু করে যতক্ষণ না এটি সূচক 1 এ পৌঁছায়। এটি সূচক 0 লুপ করতে পারে না কারণ কোনও সূচক নেই অদলবদল করার উদ্দেশ্যে 0 এর কম।
- উল্লেখ্য যে উত্পন্ন র্যান্ডম ইনডেক্স লুপ ইনডেক্স নির্বাচিত হওয়ার সম্ভাবনা রয়েছে। উদাহরণস্বরূপ, লুপটি নির্বাচিত সূচক 4 এবং সূচক 0 এর মধ্যে চলছে। র্যান্ডম সূচকটি 4 হতে দিন। তারপর সূচক 4-এর মান একই অবস্থানে থাকবে।
নিচের উদাহরণটি ফিশার-ইয়েটসকে ব্যাখ্যা করে আধুনিক শাফেল অ্যালগরিদম
উদাহরণ
<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.
