Xáo trộn (Shuffle) ngẫu nhiên List trong Java

Java cung cấp Collections.shuffle() để xáo trộn ngẫu nhiên thứ tự phần tử trong List. Dùng thuật toán Fisher-Yates (Knuth shuffle) – O(n), uniform distribution.

Cách dùng cơ bản

import java.util.*;

public class ShuffleDemo {
    public static void main(String[] args) {
        List list = new ArrayList<>(Arrays.asList("Hello", ",", "this", "is", "a", "sample"));
        System.out.println("Original: " + list);
        
        Collections.shuffle(list); // Sử dụng default Random
        System.out.println("Shuffled: " + list);
        
        // Với Random seed cố định (deterministic - cho test/reproduce)
        Collections.shuffle(list, new Random(42));
        System.out.println("Shuffled (seed 42): " + list);
    }
}

Overloads

• shuffle(List list) – dùng new Random() nội bộ.
• shuffle(List list, Random rnd) – cung cấp Random tùy chỉnh (seed, SecureRandom, ThreadLocalRandom).

Lưu ý quan trọng

• In-place: List gốc bị thay đổi. Muốn giữ nguyên → copy trước: new ArrayList<>(list).
• Chỉ làm việc với List (có index truy cập ngẫu nhiên). Không dùng cho Set, Queue (trừ khi convert to List).
• Thread-safety: Collections.shuffle không thread-safe. Nếu multi-thread truy cập list → synchronize hoặc dùng CopyOnWriteArrayList (nhưng shuffle trên nó không hiệu quả).
• Random quality: Mặc định java.util.Random đủ cho hầu hết. Dùng ThreadLocalRandom.current() (Java 7+) cho performance multi-thread. Dùng SecureRandom cho cryptographic.

Ví dụ: Shuffle mảng (Array)

Arrays không có shuffle trực tiếp. Chuyển sang List hoặc tự implement Fisher-Yates:

public static void shuffleArray(int[] arr) {
    Random rnd = ThreadLocalRandom.current();
    for (int i = arr.length - 1; i > 0; i--) {
        int j = rnd.nextInt(i + 1);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

// Hoặc dùng List
List list = Arrays.asList(1,2,3,4,5); // Fixed-size list backed by array
Collections.shuffle(list); // Shuffle mảng gốc!

Ví dụ: Random sampling (Reservoir Sampling) – không cần shuffle toàn bộ

// Lấy k phần tử ngẫu nhiên từ stream/large list (O(n) time, O(k) space)
public static  List reservoirSample(List source, int k, Random rnd) {
    List reservoir = new ArrayList<>(k);
    int i = 0;
    for (T item : source) {
        if (i < k) {
            reservoir.add(item);
        } else {
            int j = rnd.nextInt(i + 1);
            if (j < k) reservoir.set(j, item);
        }
        i++;
    }
    return reservoir;
}

ThreadLocalRandom (Java 7+) – Khuyên dùng cho multi-thread

Collections.shuffle(list, ThreadLocalRandom.current());

Tóm tắt

• Collections.shuffle(list) – đơn giản, hiệu quả, in-place.
• Cần deterministic (test) → new Random(seed).
• Multi-thread → ThreadLocalRandom.current().
• Cryptographic → SecureRandom.
• Array → tự implement Fisher-Yates hoặc wrap thành List.