[java] java.util.Random이 실제로 무작위입니까? 52를 어떻게 생성 할 수 있습니까! (계통적) 가능한 순서?

랜덤 순열을 선택하려면 질문에서 의미하는 것보다 더 많은 랜덤이 필요합니다. 설명하겠습니다.

나쁜 소식은 더 많은 무작위성이 필요하다는 것입니다.

귀하의 접근 방식의 근본적인 결함은 64 비트의 엔트로피 (임의의 시드)를 사용하여 ~ 2 ²²⁶ 가능성 중에서 선택하려고한다는 것 입니다. ~ 2 ^{226 개의} 가능성 을 공정하게 선택하려면 64 대신 226 비트의 엔트로피를 생성하는 방법을 찾아야합니다.

랜덤 비트를 생성하는 방법에는 전용 하드웨어 , CPU 명령어 , OS 인터페이스 , 온라인 서비스 등 여러 가지가 있습니다 . 당신의 질문에는 이미 64 비트를 생성 할 수 있다는 암시 적 가정이 이미 있습니다. 따라서 4 번만 수행하고 초과 비트를 자선 단체에 기부하십시오. 🙂

좋은 소식은 적은 무작위성이 필요하다는 것입니다.

226 개의 임의 비트가 있으면 나머지를 결정 론적으로 수행 할 수 있으므로 속성을 java.util.Random무의미하게 만들 수 있습니다 . 방법은 다음과 같습니다.

52 개를 모두 생성한다고 가정 해 봅시다! 순열 (나를 지니고)을 사전 식으로 정렬합니다.

순열 중 하나를 선택 모든 우리의 필요 사이에 단일 무작위 정수 0와 52!-1. 그 정수는 우리의 226 비트 엔트로피입니다. 정렬 된 순열 목록에 대한 색인으로 사용합니다. 랜덤 인덱스가 균일하게 분포 된 경우 모든 순열을 선택할 수 있다고 보장 할뿐만 아니라 동등 하게 선택됩니다 (질문이 요구하는 것보다 더 강력한 보증 임).

이제 실제로 이러한 순열을 모두 생성 할 필요는 없습니다. 가상 정렬 목록에서 임의로 선택된 위치를 고려하여 직접 하나를 생성 할 수 있습니다. 이는 Lehmer ^[1] 코드를 사용하여 O (n ² ) 시간 내에 수행 할 수 있습니다 ( 번호 매기기 순열 및 계승 수 시스템 참조 ). 여기서 n은 갑판의 크기, 즉 52입니다.

이 StackOverflow 답변 에는 C 구현이 있습니다. n = 52에 오버플로되는 몇 가지 정수 변수가 있지만 운 좋게도 Java에서는을 사용할 수 있습니다 java.math.BigInteger. 나머지 계산은 거의 그대로 기록 될 수 있습니다.

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s\n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

^[1] Lehrer 와 혼동하지 마십시오 . 🙂

답변

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);