برزدن فیشر یتس

بر زدن فیشر یتس الگوریتمی برای ایجاد جایگشت تصادفی از یک دنباله است. فرض کنید به ما آرایه ای داده شده است و می خواهیم جایگشتی تصادفی از اعضای آن آرایه به دست آوریم. این کار مانند بر زدن دسته ای ورق است و بر زدن آرایه به این معناست که هر کدام از جایگشت های ممکن، با احتمال مساوی بیایند و جایگشتی نااریب ایجاد شود. نسخهٔ اولیه پیچیدگی زمانی O ( n 2 ) دارد اما نسخهٔ جدید این الگوریتم بهینه است و زمان اجرای آن ضریبی از تعداد عناصر و خطی می باشد. [ ۱] همچنین درجا اجرا می شود و نیاز به حافظهٔ اضافی ندارد.
نسخهٔ اولیه بر زدن فیشر - یتس در سال ۱۹۳۸ توسط رونالد فیشر و فرنک یتس در کتاب جداول آماری برای تحقیقات زیستی، زراعتی، پزشکی[ ۲] منتشر شد. این الگوریتم بسیار ساده است و برای استفادهٔ مستقیم انسان ها مناسب می باشد زیرا تنها به کاغذ و خودکار نیازمند است! اما به دلیل پیچیدگی زمانی بالا توسط کامپیوترها که با دنباله های بزرگ سر و کار دارند به کار گرفته نمی شود.
در این نسخه خاصیت تصادفی توسط جدولی از اعداد تصادفی ایجاد می شود. روش ایجاد جایگشت تصادفی اعداد ۱ تا n به شرح زیر است: ۱ - اعداد یک تا n را بنویسید. ۲ - عدد تصادفی k را بین یک و تعداد اعداد خط نخورده انتخاب کنید. ( k می تواند یک و تعداد اعداد باقی مانده نیز باشد ) ۳ - k امین عدد خط نخورده را پیدا کنید و انتهای لیستی دیگر بنویسید. سپس آن را خط بزنید. ۴ - مراحل ۲ و ۳ را تکرار کنید تا تمامی اعداد خط بخورند. ۵ - دنبالهٔ اعداد ایجاد شده در لیست، جایگشتی از دنبالهٔ اولیه است. با فرض اینکه عدد تصادفی انتخاب شده در مرحلهٔ ۲ واقعاً تصادفی و نااریب باشد جایگشت ایجاد شده نیز دارای این خواص است. همچنین فیشر و یتس دربارهٔ چگونگی تولید عدد تصادفی در هر بازه ای توسط جداول از پیش مهیا شده توضیح دادند. این روش نااریب است.
فرض کنید می خواهیم جایگشتی از اعداد ۱ تا ۵ را به دست آوریم. آن ها را روی تکه کاغذی می نویسیم:
فرض کنید عدد تصادفی به دست آمده در مرحلهٔ دو ۳ باشد. با خط زدن ۳ و افزودن به لیست نهایی به نتیجهٔ زیر می رسیم:
به همین ترتیب ادامه می دهیم تا تمامی اعداد خط بخورند.
نسخهٔ جدید بر زدن فیشر یتس برای استفادهٔ کامپیوترها طراحی شده. این نسخه در سال ۱۹۶۴ توسط ریچارد داستنفلد معرفی شد[ ۳] و توسط دونالد کنوت در کتاب هنر برنامه نویسی رایانه با عنوان «الگوریتم پی»[ ۴] به شهرت رسید. به نظر می رسد آن ها از الگوریتم فیشر و یتس مطلع نبوده اند. ایدهٔ نسخهٔ جدید مشابه نسخهٔ اصلی است و بر مبنای انتخاب تصادفی می باشد. اما تفاوت جزئی آن موجب کاهش چشم گیر زمان اجرا می شود. این الگوریتم با وجود سادگی نااریب است و از حافظهٔ اضافه استفاده نمی کند. الگوریتم فشر یتس زمان غیرضروری ای را صرف پیدا کردن k امین عدد خط نخورده می کند ( خط ۳ ) . داستنفلد برای آن راه حلی ارائه کرد. در هر بار اجرای حلقهٔ دستورات عدد خط خورده را با جابه جا کردن آن با آخرین عدد خط نخورده به انتهای آرایه منتقل کنیم. این راه حل پیچیدگی زمانی بر زدن را از O ( n 2 ) به O ( n ) کاهش داد. ۱ - دنباله ایی به طول n از اعداد مورد نظر را در نظر بگیرید. ۲ - عددی تصادفی مانند m در بازهٔ انتخاب کنید. k تعداد اعدادی است که روی آن ها عملیات انجام شده؛ به عبارت دیگر تعداد حلقه های اجرا شده می باشد. ۳ - عنصر m ام را با عنصر n − k ام جابه جا کنید. ۴ - مراحل ۲ و ۳ را n − 1 دفعه تکرار کنید. ۵ - دنبالهٔ شما به جایگشتی تصادفی از دنبالهٔ اولیه تبدیل شده است.