Shuffle An Array: Trộn Mảng Ngẫu Nhiên (Fisher-Yates) Với Reset

Đề bài: Thiết kế class Solution(nums) hỗ trợ:

• reset(): Trả về mảng gốc.
• shuffle(): Trả về permutation ngẫu nhiên đều đặn (uniform) của mảng.

Thuật toán Fisher-Yates (Knuth Shuffle) - Chuẩn O(n)

Duyệt từ cuối về đầu, swap với index ngẫu nhiên ≤ i.

import random

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

# Test
obj = Solution([1,2,3])
print(obj.shuffle())  # e.g., [2,1,3]
print(obj.reset())    # [1,2,3]
print(obj.shuffle())  # e.g., [3,1,2]

Lưu ý quan trọng

• Không dùng random.shuffle() trực tiếp trên self.nums nếu muốn reset() hoạt động đúng (vì shuffle in-place).
• Luôn shuffle trên copy của original.
• Fisher-Yates đảm bảo uniform distribution: mỗi permutation xác suất 1/n!.
• Code gốc trong bài dùng random.choice swap 2 index ngẫu nhiên → KHÔNG uniform (bias).

Phân tích

• reset: O(n) copy.
• shuffle: O(n) time, O(n) space (copy).
• Có thể optimize space bằng cách shuffle in-place trên self.nums và reset bằng copy original, nhưng cần copy ở đâu đó.

Kết luận

Fisher-Yates là thuật toán shuffle chuẩn. Luôn dùng copy của original array để không làm hỏng reset. Tránh các phương pháp "swap random pairs" không uniform.