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