카드 세탁 (shuffle) 문제 상세 설명

카드 를 치고 마작 을 할 때 카드 를 뒤 섞 는 동작 이 있다.카드 세탁 문 제 는 사실 매우 간단 합 니 다. 만약 에 한 배열 에 n 개의 요소 가 있다 면 어떻게 카드 세탁 (shuffle) 알고리즘 을 설계 하여 임 의 성 을 확보 합 니까?
가장 간단 한 사 고 는 자 연 스 럽 게 새 배열 을 만 드 는 것 입 니 다. 매번 원래 배열 에 남 은 요 소 를 무 작위 로 선택 하여 새 배열 에 넣 으 면 원래 배열 이 비어 있다 는 것 을 알 수 있 습 니 다.
이런 방식 의 임 의성 을 고려 해 보 자.하나의 요소 shuffle 이후 첫 번 째 위치 에 있 을 확률 은 1n, 즉 첫 번 째 로 뽑 혔 습 니 다.두 번 째 위치 에 나타 날 확률 은:
p = p (첫 번 째 못 뽑 음)×p (두번째 뽑 기) = (1 − 1n)×1n−1=1n
이런 식 으로 미 루어 보면 이 요소 가 등 확률 로 임 의 위치 에 분배 되 고 임 의 요구 에 부합 되 는 것 을 알 수 있다.(이 부분 은 novoland 의 github 에서 온 글 을 유도 합 니 다)
이 사고방식 에 따라 카드 세탁 알고리즘 을 실현 할 때 두 가지 문제 가 있다.우선, 새 카드 더미 에 필요 한 공간;그 다음 에 요 소 는 낡은 배열 에서 새 카드 더미 로 옮 긴 후에 반드시 구멍 이 남 을 것 이 고 다음 에 카드 를 뽑 을 때 이런 구멍 위 치 를 뛰 어 넘 어야 한다.
그러나 실제 적 으로 새 카드 더미 와 낡은 카드 더미 요소 의 합 은 n 이기 때문에 전체 카드 를 섞 는 과정 은 현지에서 완성 할 수 있다.우 리 는 예전 부터 뒤로 옮 겨 다 닐 수 있 고 요소 i, 앞 i - 1 의 위치 에 대해 새로운 카드 더 미 를 구성 할 수 있 으 며 i 와 그 후속 요 소 는 오래된 카드 더미 에 속한다.오래된 카드 더미 에서 무 작위 로 요 소 를 추출 하여 i 곳 의 요소 와 교환 하면 카드 를 뽑 는 동작 을 완성 할 수 있 습 니 다.
이 알고리즘 은 Fisher – Yates shuffle 라 는 이름 이 있 습 니 다.
이론 을 말 한 후에 우 리 는 코드 를 보 자.talk is cheap, show me the code

package edu.bit.pro;

import java.util.Random;

public class Shuffle_Rand {

    public static void shuffle(int[] a) {
        Random rand = new Random();
        for(int i=a.length-1; i>0; i--) {
            int j = rand.nextInt(i+1); //   i+1

            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;

        }
    }

    public static void printArray(int[] a) {
        for(int i=0; iout.print(a[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] a = {0,1,2,3,4,5,6,7,8,9};
        System.out.println("before shuffle: ");
        printArray(a);


        System.out.println("
after shuffle: ");
        shuffle(a);
        printArray(a);
    }
}

코드 를 실행 한 후 출력 을 받 습 니 다:

before shuffle: 
0 1 2 3 4 5 6 7 8 9 
after shuffle: 
2 5 7 1 0 8 6 4 9 3 

코드 는 이해 하기 어렵 지 않 습 니 다. 조금 만 주의해 야 할 것 은 int j = rand.nextInt(i+1) 줄 입 니 다.필요 할 때 (i + 1) 를 주의 하 세 요. i 가 아 닙 니 다.제 이 제 이 요 소 는 교환 할 때 자신 을 포함 하기 때문에 이때 제 이 제 이 의 범 위 는 0 에서 i 까지 이 고 i 를 포함해 야 한다.Random 에서 nextInt 의 설명 을 살 펴 보 자.

Returns a pseudorandom, uniformly distributed value between 0 (inclusive) and the specified value(exclusive),
 drawn from this random number generator's sequence.

nextInt 방법 을 사용 할 때 인자 n 을 입력 한 후 발생 하 는 난수 의 범 위 는 0 - (n - 1) 입 니 다. the specified value (exclusive) 때 문 입 니 다.그래서 우리 위의 그 줄 코드 는 i 가 아니 라 (i + 1) 여야 합 니 다.
또한 자바 의 Collections 모듈 에 서 는 shuffle 기능 이 구현 되 었 습 니 다. 사용 하 는 알고리즘 은 바로 우리 가 방금 말 한 Fisher – Yates shuffle 입 니 다.