Fisher-Yates Shuffle Algorithm ใน JavaScript: สับสุ่ม Array ให้ Uniform

Fisher-Yates Shuffle (Modern)

อัลกอริทึมสับสุ่ม Array ให้ Uniform Distribution (ทุก Permutation โอกาสเท่ากัน) O(n) Time, O(1) Space

ขั้นตอน (In-place, Backward Loop)

1. Loop จาก Index สุดท้าย (n-1) ลงมา 1
2. สุ่ม Index j ระหว่าง 0 ถึง i (Inclusive)
3. Swap arr[i] กับ arr[j]

Implementation

<script>
  function shuffle(array) {
    // Copy หากไม่ต้องการ Mutate Original
    const arr = [...array];
    
    for (let i = arr.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1)); // 0 to i
      [arr[i], arr[j]] = [arr[j], arr[i]]; // Destructuring Swap
    }
    return arr;
  }
  
  const original = ['A','B','C','D','E','F','G','H'];
  console.log(shuffle(original)); // Random ทุกครั้ง
  console.log(original); // ไม่เปลี่ยน (เพราะ Copy)
</script>

ตัวอย่าง Output (สุ่มทุกครั้ง)

C,F,H,D,A,G,E,B

ทำไมต้อง Fisher-Yates?

• Naive Shuffle (Sort by Random): arr.sort(() => Math.random() - 0.5) → Biased! ไม่ Uniform
• Fisher-Yates: Mathematically Proven Uniform, O(n), In-place

Variants

• Durstenfeld's Version: In-place (ดูด้านบน) - Standard
• Inside-out: Build New Array พร้อม Shuffle (Streaming)
• Sattolo's Algorithm: Cycle Permutation (No Fixed Points)