การเรียงสับเปลี่ยนแบบสุ่มคือลำดับที่การเรียงลำดับของสิ่งต่างๆ ในลำดับใดๆ ก็ตาม มีโอกาสเกิดขึ้นเท่ากันโดยสุ่มกล่าวคือ เป็น ตัวแปรสุ่ม ที่มีค่าเป็นการเรียงสับเปลี่ยนของชุดวัตถุ การใช้การเรียงสับเปลี่ยนแบบสุ่มเป็นเรื่องปกติในเกมเสี่ยงโชคและในอัลกอริธึมแบบสุ่มในทฤษฎีการเข้ารหัสการเข้ารหัสลับและการจำลองตัวอย่างที่ดีของการเรียงสับเปลี่ยนแบบสุ่มคือการสับไพ่สำรับมาตรฐาน อย่างยุติธรรม ซึ่งในอุดมคติแล้วถือเป็นการเรียงสับเปลี่ยนแบบสุ่มของไพ่ 52 ใบ

อัลกอริทึมหนึ่งสำหรับการสร้างการเรียงสับเปลี่ยนแบบสุ่มของเซตขนาดn อย่างสม่ำเสมอกล่าวคือ การเรียงสับเปลี่ยนแต่ละแบบจากn ! แบบมีโอกาสปรากฏเท่ากัน คือ การสร้างลำดับโดยการสุ่มเลือกจำนวนเต็มระหว่าง 1 ถึงn (รวมทั้ง 1 และ n) อย่างต่อเนื่องและไม่ใส่คืนnครั้ง จากนั้นตีความลำดับนี้ ( x₁ _, ..., xₙ ₎เป็นการเรียงสับเปลี่ยน

${\displaystyle {\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}},}$

แสดงไว้ที่นี่ใน รูป แบบ สัญลักษณ์สองบรรทัด

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

สามารถหลีกเลี่ยงการลองใหม่ซ้ำได้โดยใช้อัลกอริธึมที่ในแต่ละ ขั้นตอนที่ iเมื่อx ₁ , ..., x _{i − 1}ถูกเลือกไปแล้ว จะเลือกหมายเลขสุ่มแบบสม่ำเสมอjจากระหว่าง 1 ถึงn − i + 1 (รวมทั้ง 1 และ n) และกำหนดให้x _iเท่ากับ หมายเลขที่มากที่สุดลำดับที่ jของหมายเลขที่ยังไม่ถูกเลือก วิธีนี้จะเลือกหมายเลขแบบสุ่มอย่างสม่ำเสมอจากหมายเลขที่เหลืออยู่ในแต่ละขั้นตอนโดยไม่ต้องลองใหม่ซ้ำ

อัลกอริทึมอย่างง่ายในการสร้างการเรียงสับเปลี่ยนของ สิ่งของ nชิ้นแบบสุ่มอย่างสม่ำเสมอโดยไม่ต้องลองใหม่ ซึ่งรู้จักกันในชื่อ การสับเปลี่ยนแบบฟิชเชอร์-เยตส์ ( Fisher–Yates shuffle ) คือการเริ่มต้นด้วยการเรียงสับเปลี่ยนใดๆ (เช่นการเรียงสับเปลี่ยนเอกลักษณ์ ) จากนั้นจึงไปยังตำแหน่งที่ 0 ถึงn − 2 (เราใช้ข้อตกลงที่ว่าองค์ประกอบแรกมีดัชนี 0 และองค์ประกอบสุดท้ายมีดัชนีn − 1) และสำหรับแต่ละตำแหน่งi ให้สลับองค์ประกอบที่อยู่ในตำแหน่งนั้นกับองค์ประกอบที่เลือกแบบสุ่มจากตำแหน่งiถึงn − 1 (ตำแหน่งสุดท้าย) รวมทั้งสองตำแหน่ง การเรียงสับเปลี่ยนใดๆ ของ องค์ประกอบ nชิ้นจะถูกสร้างขึ้นโดยอัลกอริทึมนี้ด้วยความน่าจะเป็น 1/ n ! พอดี ดังนั้นจึงได้การกระจายแบบสม่ำเสมอของการเรียงสับเปลี่ยน

unsigned uniform ( unsigned m ); /* ส่งคืนจำนวนเต็มสุ่ม 0 <= uniform(m) <= m-1 ที่มีการแจกแจงแบบเอกรูป */void initialize_and_permute ( unsigned permutation [], unsigned n ) { unsigned i ; for ( i = 0 ; i <= n -2 ; i ++ ) { unsigned j = i + uniform ( n - i ); /* จำนวนเต็มสุ่มที่ i ≤ j < n */ swap ( permutation [ i ], permutation [ j ]); /* สลับองค์ประกอบที่สุ่มเลือกกับ permutation[i] */ } }

หากuniform()ฟังก์ชันถูกนำไปใช้ในลักษณะที่เรียบง่ายเช่นrandom() % (m)นั้น จะเกิดความลำเอียงในการกระจายของการเรียงสับเปลี่ยนหากจำนวนค่าส่งคืนของฟังก์ชันrandom()ไม่ใช่พหุคูณของ m อย่างไรก็ตาม ผลกระทบนี้จะน้อยมากหากจำนวนค่าส่งคืนของrandom()ฟังก์ชันมีค่ามากกว่า m หลายเท่า

เช่นเดียวกับการนำกระบวนการสุ่มไปใช้ในทางคอมพิวเตอร์ทั้งหมด คุณภาพของการกระจายตัวที่สร้างขึ้นโดยการนำอัลกอริทึมแบบสุ่มไปใช้ เช่น การสับเปลี่ยนแบบ Fisher-Yates กล่าวคือ การกระจายตัวที่สร้างขึ้นจริงนั้นใกล้เคียงกับการกระจายตัวที่ต้องการมากน้อยเพียงใด จะขึ้นอยู่กับคุณภาพของแหล่งกำเนิดความสุ่มพื้นฐานในการนำไปใช้ เช่นตัวสร้างเลขสุ่มเทียมหรือตัวสร้างเลขสุ่มฮาร์ดแวร์มีการทดสอบความสุ่ม หลายวิธี สำหรับการเรียงสับเปลี่ยนแบบสุ่ม เช่น การทดสอบ "การเรียงสับเปลี่ยนที่ทับซ้อนกัน" ของการทดสอบ Diehardรูปแบบทั่วไปของการทดสอบดังกล่าวคือการใช้สถิติการเรียงสับเปลี่ยน บางอย่าง ซึ่งทราบการกระจายตัวในทางทฤษฎี แล้วทดสอบว่าการกระจายตัวของสถิตินั้นบนชุดของการเรียงสับเปลี่ยนที่สร้างขึ้นแบบสุ่มจากการใช้งานนั้นใกล้เคียงกับการกระจายตัวของสถิตินั้นจากการกระจายตัวจริงหรือไม่

การแจกแจงความน่าจะเป็นสำหรับจำนวนจุดคงที่ของการเรียงสับเปลี่ยนแบบสุ่มที่มีการกระจายอย่างสม่ำเสมอขององค์ประกอบn ตัว จะเข้าใกล้ การแจกแจงปัวซงที่มีค่าเฉลี่ย 1 เมื่อnเพิ่มขึ้น^{[ 1 ]}โมเมนต์n ตัวแรกของการแจกแจงนี้คือโมเมนต์ของการแจกแจงปัวซงโดยเฉพาะ ความน่าจะเป็นที่การเรียงสับเปลี่ยนแบบสุ่มไม่มีจุดคงที่ (กล่าวคือ การเรียงสับเปลี่ยนนั้นเป็นการเรียงสับเปลี่ยนที่ไม่ตรงแนว ) จะเข้าใกล้ 1/ eเมื่อnเพิ่มขึ้น

• สูตรการสุ่มตัวอย่างของอีเวนส์ — ความเชื่อมโยงกับพันธุศาสตร์ประชากร
• ฟาโรชัฟเฟิล
• ค่าคงที่โกลอมบ์-ดิคแมน
• สถิติการเรียงสับเปลี่ยนแบบสุ่ม
• อัลกอริทึมการสับเปลี่ยน — วิธีการเรียงลำดับแบบสุ่ม, วิธีการสลับเปลี่ยนแบบวนซ้ำ
• การเรียงสับเปลี่ยนแบบสุ่มเทียม

• การเรียงสับเปลี่ยนแบบสุ่มที่MathWorld
• การสร้างลำดับการเรียงสับเปลี่ยนแบบสุ่ม -- คำอธิบายโดยละเอียดและเชิงปฏิบัติของอัลกอริทึมการสับเปลี่ยนแบบ Knuth และรูปแบบต่างๆ สำหรับการสร้างk -permutations (การเรียงสับเปลี่ยนของ องค์ประกอบ kตัวที่เลือกจากรายการ) และk -subsets (การสร้างเซตย่อยขององค์ประกอบในรายการโดยไม่ใส่คืน) พร้อมรหัสเทียม