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

การสลับสุ่มฟิชเชอร์–เยตส์ (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(n2) ได้เป็น 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 โดยใช้ขั้นตอนวิธีการสลับแบบสุ่มของฟิชเชอร์ – เยตส์อันดั้งเดิม โดยจะเริ่มจากเขียนตัวเลขทั้งหมดลงในกระดาษ
 Range  Roll  Scratch  Result       1 2 3 4 5 6 7 8   

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

 Range  Roll  Scratch  Result 1–8  3  1 2 3 4 5 6 7 8  3

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

 Range  Roll  Scratch  Result 1–7  4  1 2 3 4 5 6 7 8  3 5

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

 Range  Roll  Scratch  Result 1–6  5  1 2 3 4 5 6 7 8  3 5 7 1–5  3  1 2 3 4 5 6 7 8  3 5 7 4 1–4  4  1 2 3 4 5 6 7 8  3 5 7 4 8 1–3  1  1 2 3 4 5 6 7 8  3 5 7 4 8 1 1–2  2  1 2 3 4 5 6 7 8  3 5 7 4 8 1 6       1 2 3 4 5 6 7 8  3 5 7 4 8 1 6 2

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

 Range  Roll  Scratch  Result       1 2 3 4 5 6 7 8   

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

 Range  Roll  Scratch  Result 1–8  6  1 2 3 4 5 8 7  6

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

 Range  Roll  Scratch  Result 1–7  2  1 7 3 4 5 8  2 6

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

 Range  Roll  Scratch  Result 1–6  6  1 7 3 4 5  8 2 6 1–5  1  5 7 3 4  1 8 2 6 1–4  3  5 7 4  3 1 8 2 6 1–3  3  5 7  4 3 1 8 2 6 1–2  1  7  5 4 3 1 8 2 6

ในอันสุดท้ายไม่มีอะไรที่สามารถสลับได้แล้ว (มีแค่ 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.

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