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

การสลับสุ่มฟิชเชอร์–เยตส์ (Fisher–Yates shuffle) ตั้งตามชื่อโรนัล ฟิชเชอร์ และแฟรงก์ เยตส์ ซึ่งเป็นผู้คิดค้นขั้นตอนวิธีนี้เป็นคนแรก ๆ นอกจากชื่อนี้แล้วขั้นตอนวิธีนี้ยังเป็นที่รู้จักในอีกชื่อหนึ่งคือการสลับสุ่มคนูธ (ตั้งตามชื่อโดนัลด์ คนูธ) ซึ่งขั้นตอนวิธีนี้นี้เป็นการสร้างเซตจำกัดที่มีการเรียงอย่างสุ่ม พูดง่าย ๆ คือการสลับลำดับของสมาชิกในเซตนั้นอย่างสุ่ม ๆ โดยตัวอย่างขั้นตอนวิธีนี้ที่คล้ายกันก็เช่น ขั้นตอนวิธีของซัตโตโล ซึ่งเป็นการสร้างวงกลมแบบสุ่มที่มีความยาวเท่ากับ n
ถ้ามีการสุ่ม-สร้างอย่างเหมาะสมการสลับตามขั้นตอนวิธีนี้จะเป็นไปโดยไม่มีความโน้มเอียง (unbiased) ซึ่งทุก ๆ การสลับที่เป็นไปได้จะมีโอกาสเกิดเท่า ๆ กัน ในขั้นตอนวิธีฉบับใหม่ของขั้นตอนวิธีนี้จะมีประสิทธิภาพมากกว่าฉบับเดิมในแง่ของเวลาการทำงาน, จำนวนตัวเลยที่ถูกสลับและปริมาณเนื้อที่ที่ต้องใช้
ลักษณะการทำงานของขั้นตอนวิธีการสลับแบบสุ่มของฟิชเชอร์ – เยตส์ นี้จะคล้ายกับการหยิบตั๋วออกจากหมวกแบบสุ่ม หรือการหยิบไพ่ออกจากสำรับแบบสุ่มทีละใบไปเรื่อย ๆ จนกว่าจะหมด สิ่งสำคัญที่ขั้นตอนวิธีนี้อธิบายถึงก็คือการทำให้ได้ผลลัพธ์ในลักษณะที่มีประสิทธิภาพและกระทำด้วยความระมัดระวังเพื่อการันตีได้ว่าจะได้ผลลัพธ์ที่ไม่โน้มเอียง
วิธีการดั้งเดิมของฟิชเชอร์ – เยตส์.
วิธีการนี้นำเสนอโดยโดนัล เอ ฟิชเชอร์ และแฟรงค์ เยตส์ในปี 1938 ในหนังสือ "Statistics tables for biological, agricultural and medical research" โดยวิธีที่พวกเค้านำแสนอนั้นถูกออกแบบมาให้สำหรับใช้แสดงให้เห็นในกระดาษได้ โดยต้องมีตารางตัวเลขสุ่มที่ได้คำนวณไว้ล่วงหน้าแล้วเพื่อใช้สุ่มตัวเลข วิธีการเป็นดังนี้
เพิ่มเติมคือตัวเลขสุ่มที่หยิบมาใช้ในขั้นตอนที่ 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 ตัวเดียว) จึงเสร็จสิ้นการสลับและได้ผลลัพธ์ดังที่แสดง