Bộ sưu tập của Java.shuffle đang làm gì?

Question

Gần đây tôi thấy mình cần phải chắc chắn rằng danh sách của tôi không theo thứ tự. Hibernate là đủ tốt đẹp để trả lại nó theo thứ tự hoàn hảo. Silly ngủ đông, không đọc được suy nghĩ của tôi.

Tôi nhìn API Java của tôi và nó nói với tôi phương pháp ngẫu nhiên của nó thực hiện điều này:

ngẫu nhiên permutes danh mục quy định sử dụng một nguồn mặc định của tính ngẫu nhiên.

Là george tò mò mà tôi, tôi muốn biết chính xác điều này có nghĩa là gì. Có một khóa học toán học tôi có thể làm để tìm hiểu điều này? Tôi có thể xem mã không? Java, bạn đang làm gì với ArrayList của tôi?!?!?

Cụ thể hơn, khái niệm toán học nào đang được sử dụng ở đây?

Answer 1

Có, bạn có thể xem mã; về cơ bản nó thực hiện Fisher-Yates shuffle. Dưới đây là (nhờ OpenJDK, và yay cho :-P mã nguồn mở):

public static void shuffle(List<?> list, Random rnd) { 
    int size = list.size(); 
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { 
     for (int i=size; i>1; i--) 
      swap(list, i-1, rnd.nextInt(i)); 
    } else { 
     Object arr[] = list.toArray(); 

     // Shuffle array 
     for (int i=size; i>1; i--) 
      swap(arr, i-1, rnd.nextInt(i)); 

     // Dump array back into list 
     ListIterator it = list.listIterator(); 
     for (int i=0; i<arr.length; i++) { 
      it.next(); 
      it.set(arr[i]); 
     } 
    } 
} 

Phương pháp hoán đổi:

private static void swap(Object[] x, int a, int b) { 
    Object t = x[a]; 
    x[a] = x[b]; 
    x[b] = t; 
} 

Answer 2

Các Collections javadoc đưa ra một số thông tin về các phương pháp ngẫu nhiên sử dụng.

Triển khai này duyệt qua danh sách ngược, từ phần tử cuối lên đến phần thứ hai, liên tục hoán đổi phần tử được chọn ngẫu nhiên vào "vị trí hiện tại". Các phần tử được chọn ngẫu nhiên từ phần của danh sách chạy từ phần tử đầu tiên đến vị trí hiện tại, bao gồm.

Vì vậy, nó bắt đầu ở cuối và đi vào danh sách ngược. Tại mỗi phần tử, nó dừng và hoán đổi phần tử hiện tại với phần tử trước từ danh sách. "Nguồn ngẫu nhiên mặc định" trong trường hợp này có thể là đối tượng Random được tạo bằng hạt mặc định.