Төсөөлөөд үз дээ — чи Blackjack тоглоом дээр картуудыг холиод тоглох гэж байна. Гэтэл хэрвээ үргэлж ижил дарааллаар хольдог бол тоглоом уйтгартай болно, тийм үү? Тэгвэл Fisher–Yates алгоритм яг үүнийг шийддэг! Энэ алгоритм нь жагсаалт эсвэл массив дахь элементүүдийг санамсаргүй дарааллаар хольж, тоглоомыг илүү сонирхолтой, шударга болгодог. Жишээлбэл, покер эсвэл blackjack тоглох үед картуудыг холиход ашиглагддаг бөгөөд ингэснээр ямар ч тоглогч давуу байдалгүй тэгш боломжтой болдог. Энэ алгоритмгүйгээр тоглоомууд хэт урьдчилан таамаглах боломжтой байх байсан.
Энэ нийтлэлд бид Fisher–Yates алгоритмын түүх, ажиллах зарчим, давуу болон сул талууд, хэрэглээний жишээг нарийвчлан авч үзэх болно. Ингэснээр та энэ алгоритмыг хэрхэн ашиглах талаар илүү ойлголттой болно.
Fisher–Yates алгоритм (заримдаа Knuth shuffle гэж нэрлэдэг) нь 1938 онд Английн статистикч Рональд Фишер (Ronald Fisher) ба Фрэнк Йейтс (Frank Yates) нар “Statistical Tables for Biological, Agricultural and Medical Research” номдоо анх танилцуулсан. Тэд энэ аргыг статистикийн туршилтад ашиглах зорилгоор боловсруулжээ. Тухайн үед энэ нь гар аргаар хийгддэг байсан бөгөөд жагсаалтын элементүүдийг цаасан дээр бичээд санамсаргүй байдлаар сольдог байв.
Дараа нь 1960-аад онд компьютерын шинжлэх ухааны эцэг гэгдэх Дональд Кнут (Donald Knuth) энэ алгоритмыг сайжруулж, компьютерт тохиромжтой хувилбарыг гаргажээ. Тэрээр “The Art of Computer Programming” номдоо энэ алгоритмыг дэлгэрэнгүй тайлбарласан бөгөөд өнөөгийн хэлбэрийг “modern Fisher-Yates” гэж нэрлэдэг. Кнут-ын хувилбар нь илүү үр ашигтай бөгөөд O(n) цаг зарцуулалттай. Өнөөдөр энэ алгоритм програмчлалын хэлнүүдийн стандарт сангуудад багтдаг, жишээлбэл Python-ийн random.shuffle() функц яг энэ зарчмаар ажилладаг.
Хүмүүсийн энэ алгоритмыг ашигладаг гол шалтгаан бол шударга, хурдан, энгийн арга юм. Учир нь энэ алгоритм нэг л удаа жагсаалтыг шалгадаг тул хурдан ажилладаг. Энгийнээр хэлбэл, энэ алгоритм нь жагсаалтын элементүүдийг тэгш боломжит байдлаар холино. Өөрөөр бол, ямар ч байрлал ижил магадлалтайгаар гардаг гэсэн үг юм. Мөн бусад “random shuffle” аргууд заримдаа тэгш магадлал өгдөггүй байхад, Fisher–Yates үүнийг баталгаажуулдаг. Тиймээс тоглоом, хөгжмийн тоглуулагч, өгөгдөл тестлэх систем зэрэг олон зүйлд ашиглагддаг.
Тоглоом хөгжүүлэлтэд карт холих, дүрүүдийн дараалал үүсгэх, санамсаргүй газарт spawn хийх гэх мэт зүйлсэд ашиглаж болдог.
Энэхүү алгоритмын давуу тал бол хурдан бөгөөд жагсаалтыг нэг л удаа шалгадаг. Мөн бүх дараалал тэгш магадлалтай, кодыг нь бичихэд хялбар, үр ашигтай буюу In-place тул нэмэлт санах ой шаардахгүй.
Харин сул тал нь бол санамсаргүй тоо үүсгэгч нь зөв байх ёстой. Хэрвээ алдаатай бол хольсон хөзөр нь ч мөн адил алдаатай байх болно.
Fisher–Yates алгоритм бол “санамсаргүй байдлын эзэн” гэж хэлж болно. Энэ нь тоглоом, аппликейшн, болон өгөгдөл боловсруулах олон салбарт ашиглагддаг шударга, хурдан, энгийн арга юм.
Чи Blackjack тоглоом дээр карт хольдог шиг, компьютер дотор ч яг энэ зарчмаар бүх зүйл тэгш боломжит байдлаар холигддог.
Энгийн мөртлөө гайхалтай — энэ л Fisher–Yates-ийн хүч юм.
