Collections.shuffle

shuffle

public static void shuffle (List<?> list)

Randomly permutes the specified list using a default source of randomness. All permutations occur with approximately equal likelihood.
The hedge "approximately" is used in the foregoing description because default source of randomness is only approximately an unbiased source of independently chosen bits. If it were a perfect source of randomly chosen bits, then the algorithm would choose permutations with perfect uniformity.

This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.

This method runs in linear time. If the specified list does not implement the RandomAccess interface and is large, this implementation dumps the specified list into an array before shuffling it, and dumps the shuffled array back into the list. This avoids the quadratic behavior that would result from shuffling a "sequential access" list in place.

번역

suffle 은 무작위로 선택된 요소를 "현재 위치"로 반복적으로 교체하면서 마지막 요소에서 두 번째 요소까지 목록을 역방향으로 순회합니다. 요소는 첫 번째 요소에서 현재 위치까지 무작위로 선택됩니다.

이 방법은 선형 시간으로 실행됩니다. 지정된 목록이 RandomAccess 인터페이스를 구현하지 않고 큰 경우 이 구현은 지정된 목록을 섞기 전에 배열에 덤프하고 섞인 배열을 다시 목록에 덤프합니다. 이렇게 하면 "순차 액세스" 목록을 제자리에 섞어서 발생하는 2차 동작을 방지할 수 있습니다.

Java Code

    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
            // instead of using a raw type here, it's possible to capture
            // the wildcard but it will require a call to a supplementary
            // private method
            ListIterator it = list.listIterator();
            for (Object e : arr) {
                it.next();
                it.set(e);
            }
        }
    }
    
    public static void swap(List<?> list, int i, int j) {
        // instead of using a raw type here, it's possible to capture
        // the wildcard but it will require a call to a supplementary
        // private method
        final List l = list;
        l.set(i, l.set(j, l.get(i)));
    }
    
    private static void swap(Object[] arr, int i, int j) {
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

---

궁금한 점

왜 뒤에서부터 섞을까?