การสลับสุ่มฟิชเชอร์–เยตส์

**การสลับสุ่มฟิชเชอร์–เยตส์** (Fisher–Yates shuffle) ตั้งตามชื่อโรนัล ฟิชเชอร์ และแฟรงก์ เยตส์ ซึ่งเป็นผู้คิดค้นขั้นตอนวิธีนี้เป็นคนแรก ๆ นอกจากชื่อนี้แล้วขั้นตอนวิธีนี้ยังเป็นที่รู้จักในอีกชื่อหนึ่งคือ**การสลับสุ่มคนูธ** (ตั้งตามชื่อโดนัลด์ คนูธ) ซึ่งขั้นตอนวิธีนี้นี้เป็นการสร้างเซตจำกัดที่มีการเรียงอย่างสุ่ม พูดง่าย ๆ คือการสลับลำดับของสมาชิกในเซตนั้นอย่างสุ่ม ๆ โดยตัวอย่างขั้นตอนวิธีนี้ที่คล้ายกันก็เช่น ขั้นตอนวิธีของซัตโตโล ซึ่งเป็นการสร้างวงกลมแบบสุ่มที่มีความยาวเท่ากับ n

ถ้ามีการสุ่ม-สร้างอย่างเหมาะสมการสลับตามขั้นตอนวิธีนี้จะเป็นไปโดยไม่มีความโน้มเอียง (unbiased) ซึ่งทุก ๆ การสลับที่เป็นไปได้จะมีโอกาสเกิดเท่า ๆ กัน ในขั้นตอนวิธีฉบับใหม่ของขั้นตอนวิธีนี้จะมีประสิทธิภาพมากกว่าฉบับเดิมในแง่ของเวลาการทำงาน, จำนวนตัวเลยที่ถูกสลับและปริมาณเนื้อที่ที่ต้องใช้

ลักษณะการทำงานของขั้นตอนวิธีการสลับแบบสุ่มของฟิชเชอร์ – เยตส์ นี้จะคล้ายกับการหยิบตั๋วออกจากหมวกแบบสุ่ม หรือการหยิบไพ่ออกจากสำรับแบบสุ่มทีละใบไปเรื่อย ๆ จนกว่าจะหมด สิ่งสำคัญที่ขั้นตอนวิธีนี้อธิบายถึงก็คือการทำให้ได้ผลลัพธ์ในลักษณะที่มีประสิทธิภาพและกระทำด้วยความระมัดระวังเพื่อการันตีได้ว่าจะได้ผลลัพธ์ที่ไม่โน้มเอียง

## วิธีการดั้งเดิมของฟิชเชอร์ – เยตส์

วิธีการนี้นำเสนอโดยโดนัล เอ ฟิชเชอร์ และแฟรงค์ เยตส์ในปี 1938 ในหนังสือ *Statistics tables for biological, agricultural and medical research* โดยวิธีที่พวกเค้านำแสนอนั้นถูกออกแบบมาให้สำหรับใช้แสดงให้เห็นในกระดาษได้ โดยต้องมีตารางตัวเลขสุ่มที่ได้คำนวณไว้ล่วงหน้าแล้วเพื่อใช้สุ่มตัวเลข วิธีการเป็นดังนี้
# เขียนตัวเลขตั้งแต่ 1 ถึง N
# เลือกตัวเลขสุ่ม k ซึ่งอยู่ในช่วงตั้งแต่ 1 จนถึงจำนวนตัวเลขทั้งหมดที่ยังไม่ถูกขีดฆ่าทั้งหมด
# นับจากตัวน้อยสุด ขีดฆ่าตัวที่ k โดยการนับจะนับข้ามตัวที่ขีดฆ่าทิ้งแล้วไป จากนั้นเอาไปเขียนไว้ที่อื่น
# ทำขั้นตอนที่ 2, 3 ซ้ำจนกว่าตัวเลขจะถูกขีดฆ่าทิ้งหมด
# ตอนนี้ลำดับที่เอาไปเขียนไว้ในขั้นตอนที่ 3 จะได้เป็นลำดับที่เรียงแบบสุ่มแล้ว
เพิ่มเติมคือตัวเลขสุ่มที่หยิบมาใช้ในขั้นตอนที่ 2 นั้นเป็นตัวเลขที่สุ่มและไม่มีความโน้มเอียงจริงๆ เช่นเดียวกันกับผลลัพธ์ที่ได้ นอกจากวิธีการสุ่มตัวเลขนี้แล้วฟิชเชอร์กับเยตส์ยังได้แนะถึงความเป็นไปได้ที่จะใช้วิธีที่ซับซ้อนน้อยกว่านั้นด้วย คือการเลือกตัวเลข 1 ตัวจาก 1 ถึง N แล้วทิ้งตัวที่ซ้ำไป เพื่อสร้างการสลับของตัวเลขครึ่งแรก ส่วนที่เหลือจะใช้ขั้นตอนวิธีอื่นที่ซับซ้อนกว่าในจัดการ ทั้งนี้เพราะว่าถ้าใช้วิธีเดียวกับครึ่งแรกจะเจอปัญหาเรื่องตัวซ้ำมากขึ้นจนเป็นที่น่าหงุดหงิด

## ขั้นตอนวิธีแบบใหม่
ขั้นตอนวิธีการสลับแบบใหม่ถูกนำเสนอในปี 1964 โดยริชาร์ด เดอร์สเตินเฟลด์ ในหนังสือ Communication of ACM เล่มที่ 7 ปัญหาที่ 7 และภายหลังได้รับความนิยมในตอนที่โดนัล อี คนุทเขียนไว้ในหนังสือของเขาชื่อ The Art of Computer Programming ซึ่งในการพิมพ์ครั้งแรก ทั้งเดอร์สเตินเฟลด์และคนุทยังไม่มีใครรู้ถึงขั้นตอนวิธีของฟิชเชอร์ – เยตส์ แต่ในการพิมพ์ครั้งหลังจากนั้นคนุทได้เอ่ยถึงงานเขียนของฟิชเชอร์ – เยตส์ ในหนังสือของเขา
ขั้นตอนวิธีนี้ออกแบบมาสำหรับใช้กับคอมพิวเตอร์ และมีลักษณะต่างจากขั้นตอนวิธีของฟิชเชอร์ – เยตส์ ในรายละเอียดที่เล็กน้อย แต่ทว่าสำคัญ นั่นคือการแก้ปัญหาเรื่องการใช้เวลานานในการนับตัวเลขที่เหลืออยู่ในขั้นตอนที่ 3 ของ ฟิชเชอร์ – เยตส์ ซึ่งเดอร์สเตินเฟลด์ได้แก้ปัญหานี้โดยการย้ายตัวที่ขีดฆ่าทิ้งแล้วไปไว้หลังสุดของลำดับ โดยการสลับตัวเลขนั้นกับตัวเลขตัวสุดท้ายที่ยังไม่ถูกขีดฆ่าทิ้งในทุกๆรอบที่ทำ ถ้าดูในแง่ของเวลา (time complexity) ในการทำงานของขั้นตอนวิธีจะลดจากเดิม *O*(*n*2) ได้เป็น *O*(*n*) ความเปลี่ยนแปลนี้นำไปสู่ขั้นตอนวิธีดังข้างล่าง (สำหรับลำดับที่เรียงจาก 0)

 To shuffle an array *a* of *n* elements (indexes 0..n-1):
   **for** *i* **from** *n* − 1 **downto** 1 **do**
        *j* ← random integer with 0 ≤ *j* ≤ *i*
        exchange *a*[*j*] and *a*[*i*]

## ขั้นตอนวิธีแบบอินไซด์ – เอาต์
การสลับแบบพร้อมสำหรับใช้งาน (in-place shuffle) นั่นคือได้รับแถวลำดับแบบที่ให้ค่าเริ่มต้นมาอยู่แล้ว จากนั้นจะสลับแถวลำดับนั้นให้เลย โดยไม่ได้คัดลอกแถวลำดับนั้นออกมาอีกอันแล้วสลับให้ การทำแบบนี้มีข้อดีในกรณีที่แถวลำดับที่จะสลับมีขนาดใหญ่
สำหรับการที่จะให้ค่าเริ่มต้นและสลับไปเลยในเวลาเดียวกันจะต้องใช้วิธีที่มีประสิทธิภาพมากกว่านั้นหน่อยคือการทำแบบ “อินไซด์-เอาต์” ในการทำแบบนี้จะนำข้อมูลตัวที่ i ไปไว้ที่ตำแหน่งที่สุ่มใน i ตัวแรกของข้อมูล ซึ่งก่อนหน้านี้ก็ให้ย้ายข้อมูลตัวที่เดิมอยู่ตำแหน่งนั้นไปยังตำแหน่งที่ i ส่วนในกรณีที่ข้อมูลตัวที่ i สุ่มได้วางตำแหน่งที่ i พอดีก็ไม่เป็นไรเพราะสุดท้ายข้อมูลตัวที่ i ก็จะถูกวางทับที่ตำแหน่งที่ i อยู่ดี วิธีการแบบนี้ทำให้ไม่ต้องมีการใส่ค่าเริ่มต้นให้แถวลำดับก่อน และในกรณีทั่ว ๆ ไปต้นฉบับของข้อมูลสามารถแทนจากค่าจำนวนเต็ม 1 ถึง n-1 ด้วยฟังก์ชันได้ เพราะว่าระหว่างทำงานค่าของมันไม่เคยถูกเปลี่ยนแปลง

 To initialize an array *a* of *n* elements to a randomly shuffled copy of *source*, both 0-based:
   *a*[0] ← *source*[0]
   **for** *i* **from** 1 **to** *n* − 1 **do**
       *j* ← random integer with 0 ≤ *j* ≤ *i*
       *a*[*i*] ← *a*[*j*]
       *a*[*j*] ← *source*[*i*]

ซึ่งสามารถพิสูจน์ให้เห็นว่าไม่มีความโน้มเอียงได้ด้วยการอุปนัย คือในลำดับแต่ละลำดับที่แตกต่างกัน n! แบบที่ได้จากการสุ่มจะได้การสับเปลี่ยนของค่าที่แตกต่างกัน ดังนั้นแต่ละรูปแบบของของการสับเปลี่ยนเหล่านี้จึงเกิดขึ้นแบบละครั้งเท่านั้น

## ตัวอย่าง
### วิธีการที่ทำด้วยกระดาษและดินสอ
ต้องการจะสับเปลี่ยนตัวเลข 1 ถึง 8 โดยใช้ขั้นตอนวิธีการสลับแบบสุ่มของฟิชเชอร์ – เยตส์อันดั้งเดิม โดยจะเริ่มจากเขียนตัวเลขทั้งหมดลงในกระดาษ

จากนั้นจะสุ่มเลข k ตัวหนึ่งขึ้นมา โดยเป็นเลขตั้งแต่ 1 ถึง 8 สมมติว่าได้ 3 ก็ขีดฆ่าตัวที่ k ทิ้งไป (ในที่นี้คือตัวที่ 3 และตัวที่ขีดทิ้งไปคือเลข 3) แล้วเอาไปเขียนในช่องผลลัพธ์

จากนั้นเราก็หยิบตัวเลขสุ่มตัวที่ 2 ซึ่งต้องเป็นเลขตั้งแต่ 1 ถึง 7 คราวนี้ได้ 4 เราก็ขีดฆ่าตัวเลขตัวที่ 4 ที่ยังไม่ได้ถูกขีดฆ่า นั่นก็คือตัวเลข 5 และเพิ่มตัวเลขนั่นเข้าไปในผลลัพธ์

หยิบตัวเลขสุ่มตัวต่อไปจากตัวเลข 1 ถึง 6 จากนั้นก็ 1 ถึง 5 ทำไปเรื่อย ๆ ทำซ้ำการขีดฆ่าตัวเลขเหมือนข้างบน:

### วิธีการแบบใหม่
คราวนี้เราจะทำแบบเดียวกัน แต่เปลี่ยนไปใช้ขั้นตอนวิธีของเดอร์สเตินเฟลด์แทน ซึ่งจะใช้การสุ่มเลขแล้วสลับตัวนั้นกับตัวท้ายสุดที่ยังไม่ได้เลือกมาสลับ ตอนเริ่มก็เหมือนกันคือเขียนเลข 1 ถึง 8 เพื่อความชัดเจนเราจะใช้เส้นดิ่งในการแยกส่วนที่เลือกไปสลับแล้วกับส่วนที่ยังไม่ได้สลับ

ในการสุ่มครั้งแรกจะใช้เลขในช่วง 1 ถึง 8 ซึ่งได้เลข 6 ดังนั้นเราจึงจะสลับตัวเลขตัวที่ 6 กับตัวเลขตัวที่ 8 ในแถวลำดับ

ครั้งต่อไปเราสุ่มเลขในช่วง 1 ถึง 7 และผลออกมาได้ 2 เราจึงสลับตัวที่ 2 กับ ตัวที่ 7 และทำต่อ

ในการสุ่มครั้งต่อไป เราจะสุ่มเลขในช่วง 1 ถึง 6 และบังเอิญได้เลข 6 พอดี ซึ่งหมายถึงว่าเราได้ตำแหน่งเดียวกับที่จะสลับ (ซึ่งขณะนี้คือเลข 8) ทำให้ได้ตำแหน่งเหมือนเดิม จากนั้นเราก็ทำเหมือนๆเดิมจนกระทั่งการสลับเสร็จสิ้น

ในอันสุดท้ายไม่มีอะไรที่สามารถสลับได้แล้ว (มีแค่ 7 ตัวเดียว) จึงเสร็จสิ้นการสลับและได้ผลลัพธ์ดังที่แสดง

## อ้างอิง
# ^ Fisher, R.A.; Yates, F. (1948) [1938]. Statistical tables for biological, agricultural and medical research (3rd ed.). London: Oliver & Boyd. pp. 26–27. OCLC 14222135. (note: 6th edition,ISBN 0-02-844720-4)
# ^ Durstenfeld, Richard (July 1964). "Algorithm 235: Random permutation". Communications of the ACM 7 (7): 420. doi:10.1145/364520.364540.
# ^ Knuth, Donald E. (1969). The Art of Computer Programming volume 2: Seminumerical algorithms. Reading, MA: Addison–Wesley. pp. 124–125. OCLC 85975465.
# ^ Knuth (1998) [1969]. The Art of Computer Programming vol. 2 (3rd ed.). Boston: Addison–Wesley. pp. 145–146. ISBN 0-201-89684-2. OCLC 38207978.
# ^ Black, Paul E. (2005-12-19). "Fisher–Yates shuffle". Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Retrieved 2007-08-09.
# ^ Wilson, Mark C. (2004-06-21). "Overview of Sattolo's Algorithm". In F. Chyzak (ed.). INRIA Research Report. 5542. Algorithms Seminar 2002–2004, summary by Éric Fusy.. pp. 105–108. ISSN 0249-6399.
# ^ "A simple shuffle that proved not so simple after all". require ‘brain’. 2007-06-19. Retrieved 2007-08-09.
# ^ "Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot". Rob Weir: An Antic Disposition. 2010-02-27. Retrieved 2010-02-28.
# ^ "Writing a sort comparison function, redux". require ‘brain’. 2009-05-08. Retrieved 2009-05-08.

หมวดหมู่:วิธีมอนเตการ์โล
หมวดหมู่:ขั้นตอนวิธี
หมวดหมู่:การสุ่ม