Shuffle an Array: สุ่มลำดับ Array (Fisher-Yates Shuffle)

โจทย์

ออกแบบ Class รองรับ:

• reset(): คืน array ต้นฉบับ
• shuffle(): คืน array ที่สุ่มลำดับ (Uniform random permutation)

อัลกอริทึม: Fisher-Yates Shuffle (Knuth Shuffle) - O(n)

สุ่มแบบ unbiased ทุก permutation โอกาสเท่ากัน:

for i from n-1 down to 1:
    j = random integer in [0, i]
    swap(arr[i], arr[j])

การติดตั้ง (Python Implementation)

import random
import copy

class Solution:
    def __init__(self, nums: list[int]):
        self.original = nums[:]  # Keep copy of original
        self.nums = nums[:]      # Working array
    
    def reset(self) -> list[int]:
        self.nums = self.original[:]
        return self.nums
    
    def shuffle(self) -> list[int]:
        # Fisher-Yates shuffle
        for i in range(len(self.nums) - 1, 0, -1):
            j = random.randint(0, i)
            self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
        return self.nums

# ทดสอบ
ob = Solution([1,2,3])
print(ob.shuffle())  # e.g., [2,1,3]
print(ob.reset())    # [1,2,3]
print(ob.shuffle())  # e.g., [3,1,2]
print(ob.shuffle())  # e.g., [1,3,2]

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

[2, 1, 3]
[1, 2, 3]
[3, 1, 2]
[1, 3, 2]

ทำไม Fisher-Yates ถูกต้อง? (Correctness)

• มี n! permutations ทั้งหมด
• Step i: เลือก j จาก 0..i (i+1 choices)
• Total choices: n × (n-1) × ... × 1 = n! → ทุก permutation ได้โอกาสเท่ากัน 1/n!
• In-place, O(n) time, O(1) extra space

Common Mistakes (Biased Shuffles)

# ❌ WRONG: Swap with random index in full range
for i in range(n):
    j = random.randint(0, n-1)
    swap(arr[i], arr[j])  # BIASED! Not uniform

# ❌ WRONG: Sort by random key
arr.sort(key=lambda x: random.random())  # BIASED! Not uniform (depends on sort stability)

# ✅ CORRECT: Fisher-Yates
for i in range(n-1, 0, -1):
    j = random.randint(0, i)
    swap(arr[i], arr[j])

Python Built-in Alternative

import random

def shuffle_builtin(arr):
    shuffled = arr[:]
    random.shuffle(shuffled)  # Uses Fisher-Yates internally
    return shuffled

Complexity

• reset(): O(n) time, O(n) space (copy)
• shuffle(): O(n) time, O(1) extra space (in-place)
• Constructor: O(n) time, O(n) space

สรุป

Shuffle an Array ใช้ Fisher-Yates (Knuth) Shuffle เป็นอัลกอริทึมมาตรฐานสำหรับ unbiased permutation ใน O(n) time ใช้ random.randint(0, i) ในลูปย้อนหลัง

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ