Java의 Collections.shuffle이 무엇을하고 있습니까?

Question

나는 최근에 내 목록이 순서에 맞지 않았 음을 알게되었다. Hibernate는 완벽한 순서로 반환하기에 충분히 좋았다. 어리석은 동면, 내 마음을 읽지 마라.

내 자바 API를 쳐다 보면서 그것의 셔플 방법이 수행 저에게 말한다 :

는 디폴트의 random number generation의 원을 사용해, 지정된리스트의 순서를 무작위로 바꾸어 넣습니다.

내가 호기심이 넘치는 조지라는 사실을 정확히 알고 싶습니다. 이것을 배우기 위해 내가 수강 할 수있는 수학 코스가 있습니까? 코드를 볼 수 있습니까? 자바, 내 ArrayList에 대해 뭐하고 있니?!?!?

더 구체적으로 말하면 어떤 수학 개념이 사용되고 있습니까?

Answer 1

예, 코드를 볼 수 있습니다. 그것은 기본적으로 Fisher-Yates shuffle입니다. 여기가 (덕분에 오픈 JDK, 오픈 소스 - P에 대한 야호)입니다 :

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]); 
     } 
    } 
} 

스왑 방법 :

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

Answer 2

Collections의 JavaDoc 사용 셔플 방법에 대한 몇 가지 정보를 제공합니다.

이 구현은 마지막 요소에서 두 번째 요소까지 목록을 거꾸로 가로 질러 임의로 선택한 요소를 "현재 위치"로 반복 스와핑합니다. 요소는 목록의 첫 번째 요소에서 현재 위치까지 실행되는 부분에서 무작위로 선택됩니다.

그래서 마지막부터 시작하여 목록을 뒤로 이동합니다. 각 요소에서 현재 요소를 중지하고 목록에서 선행 요소로 바꿉니다. 이 경우 "기본 무작위 소스"는 기본 시드로 생성 된 Random 개체 일 수 있습니다.