نمایش مبدأ برای برزدن فیشر یتس

'''بر زدن فیشر یتس'''
[[الگوریتم]]ی برای ایجاد [[جایگشت]] تصادفی از یک [[دنباله]] است.
{{سخ}}
فرض کنید به ما آرایه‌ای داده شده‌است و می‌خواهیم جایگشتی تصادفی از اعضای آن آرایه به دست آوریم. این کار مانند بر زدن دسته‌ای ورق است و بر زدن آرایه به این معناست که هر کدام از جایگشت‌های ممکن، با [[احتمال]] مساوی بیایند و جایگشتی [[سوگیری|نااریب]] ایجاد شود.
{{سخ}}
نسخهٔ اولیه [[پیچیدگی]] زمانی
<math>O(n^2)</math>
دارد اما نسخهٔ جدید این الگوریتم بهینه است و زمان اجرای آن ضریبی از تعداد عناصر و خطی می‌باشد.<ref name="nist">{{cite web
| first = Paul E.
| last = Black
| work = Dictionary of Algorithms and Data Structures
| title = Fisher–Yates shuffle
| publisher = National Institute of Standards and Technology
| url = https://xlinux.nist.gov/dads/HTML/fisherYatesShuffle.html
| date = 2005-12-19
| accessdate = 2007-08-09
}}</ref>
همچنین [[الگوریتم درجا|درجا]] اجرا می‌شود و نیاز به حافظهٔ اضافی ندارد.

== روش اصلی بر زدن فیشر یتس ==
نسخهٔ اولیه بر زدن فیشر-یتس در سال ۱۹۳۸ توسط [[رونالد فیشر]] و فرنک یتس در کتاب جداول آماری برای تحقیقات زیستی، زراعتی، پزشکی<ref name="fisheryates">{{cite book
| last=Fisher |first=Ronald A. |last2=Yates |first2=Frank
| title = Statistical tables for biological, agricultural and medical research
| url=https://archive.org/details/b32847592 | origyear = 1938
| edition = 3rd
| year = 1948
| pages = [https://archive.org/details/b32847592/page/26 26]–27
| publisher = Oliver & Boyd
| location = London
| oclc = 14222135
}}</ref> منتشر شد.
{{سخ}}
این الگوریتم بسیار ساده است و برای استفادهٔ مستقیم انسان‌ها مناسب می‌باشد زیرا تنها به کاغذ و خودکار نیازمند است! اما به دلیل [[پیچیدگی زمانی]] بالا توسط کامپیوترها که با دنباله‌های بزرگ سر و کار دارند به کار گرفته نمی‌شود.

در این نسخه خاصیت تصادفی توسط جدولی از اعداد تصادفی ایجاد می‌شود. روش ایجاد جایگشت تصادفی اعداد ۱ تا
n
به شرح زیر است:
{{سخ}}
'''۱-'''
اعداد یک تا
n
را بنویسید.
{{سخ}}
'''۲-'''
عدد تصادفی
k
را بین یک و تعداد اعداد خط نخورده انتخاب کنید.
(k
می‌تواند یک و تعداد اعداد باقی‌مانده نیز باشد)
{{سخ}}
'''۳-'''
k
امین عدد خط نخورده را پیدا کنید و انتهای لیستی دیگر بنویسید. سپس آن را خط بزنید.
{{سخ}}
'''۴-'''
مراحل ۲ و ۳ را تکرار کنید تا تمامی اعداد خط بخورند.
{{سخ}}
'''۵-'''
دنبالهٔ اعداد ایجاد شده در لیست، جایگشتی از دنبالهٔ اولیه است.
{{سخ}}
با فرض اینکه عدد تصادفی انتخاب شده در مرحلهٔ ۲ واقعاً تصادفی و [[سوگیری|نااریب]] باشد جایگشت ایجاد شده نیز دارای این خواص است. همچنین فیشر و یتس دربارهٔ چگونگی تولید عدد تصادفی در هر بازه‌ای توسط جداول از پیش مهیا شده توضیح دادند. این روش [[سوگیری|نااریب]] است.

=== مثال ===
فرض کنید می‌خواهیم جایگشتی از اعداد ۱ تا ۵ را به دست آوریم. آن‌ها را روی تکه کاغذی می‌نویسیم:
{| class="wikitable"
|-
! دامنه !! عدد تصادفی !! کاغذ !! لیست نهایی
|-
| || ۵ ۴ ۳ ۲ ۱ || ||
|}
فرض کنید عدد تصادفی به دست آمده در مرحلهٔ دو ۳ باشد. با خط زدن ۳ و افزودن به لیست نهایی به نتیجهٔ زیر می‌رسیم:
{| class="wikitable"
|-
! دامنه !! عدد تصادفی !! کاغذ !! لیست نهایی
|-
|[۵ ،۱] || ۳ ||
۵ ۴
{{font color | red | ۳}}
۲ ۱
|| ۳
|}
به همین ترتیب ادامه می‌دهیم تا تمامی اعداد خط بخورند.
{| class="wikitable"
|-
! دامنه !! عدد تصادفی !! کاغذ !! لیست نهایی
|-
|[۴ ،۱] || ۱ ||
۵ ۴
{{font color | red | ۳}}
۲
{{font color | red | ۱}}
|| ۱ ۳
|}

{| class="wikitable"
|-
! دامنه !! عدد تصادفی !! کاغذ !! لیست نهایی
|-
|[۳ ،۱] || ۳ ||
{{font color | red | ۵}}
۴
{{font color | red | ۳}}
۲
{{font color | red | ۱}}
|| ۵ ۱ ۳
|}

{| class="wikitable"
|-
! دامنه !! عدد تصادفی !! کاغذ !! لیست نهایی
|-
|[۲ ،۱] || ۱ ||
{{font color | red | ۵}}
۴
{{font color | red | ۳}}
{{font color | red | ۲}}
{{font color | red | ۱}}
|| ۲ ۵ ۱ ۳
|}

{| class="wikitable"
|-
! دامنه !! عدد تصادفی !! کاغذ !! لیست نهایی
|-
|[۱ ،۱] || ۱ ||
{{font color | red | ۵}}
{{font color | red | ۴}}
{{font color | red | ۳}}
{{font color | red | ۲}}
{{font color | red | ۱}}
|| ۴ ۲ ۵ ۱ ۳
|}

== نسخهٔ جدید الگوریتم فیشر یتس ==
نسخهٔ جدید بر زدن فیشر یتس برای استفادهٔ کامپیوترها طراحی شده. این نسخه در سال ۱۹۶۴ توسط ریچارد داستنفلد معرفی شد<ref name="cacm">{{Cite journal | last1 = Durstenfeld |first1 = R. | title = Algorithm 235: Random permutation | doi = 10.1145/364520.364540 | journal = Communications of the ACM | volume = 7 | issue = 7 | pages = 420 | date=July 1964 | pmid = | pmc =}}</ref>
و توسط [[دانلد کنوت|دونالد کنوت]] در کتاب [[هنر برنامه‌نویسی رایانه]] با عنوان «الگوریتم پی»<ref name="knuth">{{cite book
| series=The Art of Computer Programming |volume=2 |title=Seminumerical algorithms
| first = Donald E.
| last = Knuth
| pages = 139–140
| year = 1969
| publisher = Addison–Wesley
| location = Reading, MA
| oclc = 85975465
}}</ref>
به شهرت رسید. به نظر می‌رسد آن‌ها از الگوریتم فیشر و یتس مطلع نبوده‌اند.
{{سخ}}
ایدهٔ نسخهٔ جدید مشابه نسخهٔ اصلی است و بر مبنای انتخاب تصادفی می‌باشد. اما تفاوت جزئی آن موجب کاهش چشم‌گیر زمان اجرا می‌شود. این الگوریتم با وجود سادگی نااریب است و از حافظهٔ اضافه استفاده نمی‌کند.
{{سخ}}
الگوریتم فشر یتس زمان غیرضروری‌ای را صرف پیدا کردن k امین عدد خط نخورده می‌کند (خط ۳). داستنفلد برای آن راه حلی ارائه کرد. در هر بار اجرای حلقهٔ دستورات عدد خط خورده را با جابه‌جا کردن آن با آخرین عدد خط نخورده به انتهای آرایه منتقل کنیم. این راه حل پیچیدگی زمانی بر زدن را از
<math>O(n^2)</math>
به
<math>O(n)</math> کاهش داد.
{{سخ}}
'''۱-'''
دنباله ایی به طول
n
از اعداد مورد نظر را در نظر بگیرید.
{{سخ}}
'''۲-'''
عددی تصادفی مانند
<math>m</math>
در بازهٔ
<math>[1, n - k]</math> انتخاب کنید.
k
تعداد اعدادی است که روی آن‌ها عملیات انجام شده؛ به عبارت دیگر تعداد حلقه‌های اجرا شده می‌باشد.
{{سخ}}
'''۳-'''
عنصر
<math>m</math>ام را با عنصر
<math>n - k</math>ام جابه‌جا کنید.
{{سخ}}
'''۴-'''
مراحل ۲ و ۳ را
<math>n - 1</math> دفعه تکرار کنید.
{{سخ}}
'''۵-'''
دنبالهٔ شما به جایگشتی تصادفی از دنبالهٔ اولیه تبدیل شده‌است.

=== مثال ===
فرض کنید دنبالهٔ مورد نظر ۵عضوی باشد؛ مثلاً
<math>\{A_1, A_2, A_3, A_4, A_5\}</math>
{| class="wikitable"
|-
! دامنه !! عدد تصادفی !! دنباله پیش از تغییر !! دنباله پس از تغییر
|-
| [۵ ،۱]
|| ۲
|| <math>\{A_1, \frac{A_2}{}, A_3, A_4, \frac{A_5}{}\}</math>
|| <math>\{A_1, A_5, A_3, A_4, A_2\}</math>
|}

{| class="wikitable"
|-
! دامنه !! عدد تصادفی !! دنباله پیش از تغییر !! دنباله پس از تغییر
|-
| [۴ ،۱]
|| ۳
|| <math>\{A_1, A_5, \frac{A_3}{}, \frac{A_4}{}, A_2\}</math>
|| <math>\{A_1, A_5, A_4, A_3, A_2\}</math>
|}
{| class="wikitable"
|-
! دامنه !! عدد تصادفی !! دنباله پیش از تغییر !! دنباله پس از تغییر
|-
| [۳ ،۱]
|| ۳
|| <math>\{A_1, A_5, \frac{A_4}{}, A_3, A_2\}</math>
|| <math>\{A_1, A_5, A_4, A_3, A_2\}</math>
|}

{| class="wikitable"
|-
! دامنه !! عدد تصادفی !! دنباله پیش از تغییر !! دنباله پس از تغییر
|-
| [۲ ،۱]
|| ۱
|| <math>\{\frac{A_1}{}, \frac{A_5}{}, A_4, A_3, A_2\}</math>
|| <math>\{A_5, A_1, A_4, A_3, A_2\}</math>
|}

=== نمونه کد ===
کد زیر به زبان پایتون نوشته شده:<ref>{{cite web
| title = Shuffle a given array using Fisher–Yates shuffle Algorithm
| url = https://www.geeksforgeeks.org/shuffle-a-given-array-using-fisher-yates-shuffle-algorithm/
}}</ref>
{{چپ‌چین}}
 # Python Program to shuffle a given array
 import random

 # A function to generate a random permutation of arr[]
 def randomize (arr, n):
  # Start from the last element and swap one by one. We don't
  # need to run for the first element that's why i > 0
  for i in range(n-1,0,-1):
  # Pick a random index from 0 to i
  j = random.randint(0,i+1)

  # Swap arr[i] with the element at random index
  arr[i],arr[j] = arr[j],arr[i]
  return arr

 # Driver program to test above function.
 arr = [1, 2, 3, 4, 5, 6, 7, 8]
 n = len(arr)
 print(randomize(arr, n))

 # This code is contributed by Pratik Chhajer
{{پایان چپ‌چین}}
خروجی کد:
{{چپ‌چین}}
 7 8 4 6 3 1 2 5
{{پایان چپ‌چین}}

== برخی کاربردها ==
=== مولدهای اعداد تصادفی سخت‌افزاری ===
معمولاً بین بیت‌های اعداد تولیدشده توسط [[تولید اعداد تصادفی|مولدهای اعداد تصادفی]] که به‌طور سخت‌افزاری پیاده‌سازی شده‌اند، [[همبستگی]] وجود دارد.<ref>{{cite
|
author = Markus Dichtl
|
title =Cryptographic Shuffling of Random and Pseudorandom Sequences
|
book-title = Symmetric Cryptography
|
year = 2007
|
editor =Eli Biham and Helena Handschuh and Stefan Lucks and Vincent Rijmen
|
number =07021
|
series =Dagstuhl Seminar Proceedings
|
ISSN =1862-4405
|
publisher =Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany
|
URL =http://drops.dagstuhl.de/opus/volltexte/2007/1014
}}</ref>
{{سخ}}
مهاجم‌ها با یافتن این بیت‌ها می‌توانند به ما آسیب بزنند. برزدن [[بیت]]‌های عدد تولید شده می‌تواند این مشکل را بر طرف کند زیرا هربار بیت‌های همبسته به مکان‌های متفاوتی می‌روند و مهاجم نمی‌تواند آن‌ها را شناسایی کند. البته بر زدن یکی از مشکلات عمدهٔ [[:en:Hardware random number generator|مولدهای اعداد تصادفی سخت‌افزاری]] که اریب بودن آنهاست را حل نمی‌کند. این مولدها بیت صفر را به [[احتمال]] ۰٫۵ تولید نمی‌کنند و با برزدن تعداد صفر و یک‌ها تغییر نمی‌کند و مولد همچنان [[سوگیری|اریب]] باقی می‌ماند.

=== مرتب‌سازی ساختگی ===
کلیت الگوریتم به هم ریختن تصادفی آرایه و تولید جایگشت‌های تصادفی تا رسیدن به آرایهٔ مرتب‌شده‌است. این الگوریتم بهینه نیست و در بدترین حالت می‌تواند به اتمام نرسد و زمان بی‌نهایت داشته‌باشد.

== تولید عدد تصادفی در بازهٔ دلخواه ==
[[پرونده:Modula_bias_random_numbers.png|بندانگشتی|فرض کنید مولد اعداد تصادفی، اعداد صحیح در بازهٔ [۱۰ ،۱] تولید کند. استفاده از روش باقی‌مانده برای به دست آوردن اعداد صحیح تصادفی در بازهٔ [۴ ،۱] مناسب نمی‌باشد زیرا احتمال آمدن این اعداد یکسان نیست.]]
علاوه بر توجه به الگوریتم فیشر یتس باید به الگوریتم به کارگرفته‌شده برای تولید عدد تصادفی در مرحلهٔ دو نیز توجه کنیم. اریب بودن الگوریتم مذکور موجب اریب شدن جایگشت نهایی می‌شود.
معمولاً مولدهای اعداد تصادفی، اعدادی در بازهٔ
[
<math>Max</math>
,
۰]
تولید می‌کنند. یکی از روش‌های معمول برای پیدا کردن عدد تصادفی در بازهٔ
[
<math>k</math>
,
۱]
استفاده از روش باقی‌مانده می‌باشد. (
<math>k</math>
می‌تواند تعداد اعداد خط نخورده در روش اصلی فیشر یتس یا تعداد حلقه‌های باقی‌مانده در نسخه جدید باشد)
این روش در حالت کلی مناسب نمی‌باشد و نتیجهٔ نهایی ما را اریب می‌کند.
{{سخ}}
فرض کنید مولد، عدد تصادفی صحیح
r
را در بازهٔ
[
<math>Max</math>
,
۰]
تولید کند. روش باقی‌مانده
<math>1 + (r \% k)</math>
را به عنوان عدد تصادفی در بازهٔ
[
<math>k</math>
,
۱]
خروجی می‌دهد. (
<math>r \% k</math> باقی‌ماندهٔ تقسیم <math>r</math> بر <math>k</math> می‌باشد)
{{سخ}}
به‌طور مثال فرض کنید مولد، عددی در بازهٔ
[۹۹
,
۰]
تولید کند و ما عددی در بازهٔ
[۱۵
,
۱]
بخواهیم. اگر [[عدد صحیح|اعداد صحیح]] بازهٔ
[۹۹
,
۰]
را بر ۱۵ تقسیم و باقی‌مانده را با یک جمع کنیم، اعداد یک تا ده، ۷ مرتبه و سایر اعداد ۶ مرتبه ظاهر می‌شوند؛ زیرا ۱۰۰ بر ۱۵ بخش‌پذیر نیست. پس توزیع اعداد تصادفی تولید شده در بازهٔ
[۱۵
,
۱]
یکنواخت نیست و اریب می‌باشد.

== لینک‌های مرتبط ==
{{Div col|colwidth=22em}}
*[https://www.researchgate.net/profile/Dhritikesh_Chakrabarty/publication/323557253_Random_Numbers_Tables_Due_to_Tippet_Fisher_Yates_Kendall_Smith_and_Rand_Corporation_Comparison_of_Degree_of_Randomness_by_Run_Test/links/5ab3c156aca2721710036ebf/Random-Numbers-Tables-Due-to-Tippet-Fisher-Yates-Kendall-Smith-and-Rand-Corporation-Comparison-of-Degree-of-Randomness-by-Run-Test.pdf?origin=publication_detail Random Numbers Tables Due to Tippet, Fisher & Yates, Kendall & Smith and Rand Corporation]<ref>{{cite
|
author = Chakrabarty D
|
title = Random Numbers Tables Due to Tippet, Fisher & Yates, Kendall & Smith and Rand Corporation: Comparison of Degree of Randomness by Run Test. J Biostat Biometric App 3 (1): 103
|
year = 2018
|
ISSN = 2348-9820
|
issue = 1
|
volume = 3
|
publisher =Journal of Biostatistics and Biometric Applications
|
URL =https://www.researchgate.net/profile/Dhritikesh_Chakrabarty/publication/323557253_Random_Numbers_Tables_Due_to_Tippet_Fisher_Yates_Kendall_Smith_and_Rand_Corporation_Comparison_of_Degree_of_Randomness_by_Run_Test/links/5ab3c156aca2721710036ebf/Random-Numbers-Tables-Due-to-Tippet-Fisher-Yates-Kendall-Smith-and-Rand-Corporation-Comparison-of-Degree-of-Randomness-by-Run-Test.pdf?origin=publication_detail
}}</ref>
*[https://www.youtube.com/watch?v=54rMYC2pEtw&feature=youtu.be&t=76 video explanation of the Fisher-Yates by Prof Sedgewick]
*[https://eprint.iacr.org/2015/664.pdf Secure Multi-Party Shuffling]
* [[تولید اعداد تصادفی]]
* [[مرتب‌سازی ساختگی]]
*[https://teorica.fis.ucm.es/ft8/tablern2.pdf نمونه جدول اعداد تصادفی]
{{Div col end}}

== منابع ==
{{پانویس|۱}}
[[رده:الگوریتم‌های ترکیبیاتی]]
[[رده:الگوریتم‌های تصادفی]]
[[رده:جایگشت‌ها]]
[[رده:روش‌های مونت‌کارلو]]