Беспристрастное перемешивание случайных массивов

Question

Когда я хочу перетасовать массив чисел в массиве "perm" из [1...n], я написал на Java:

      int[] perm = new int[n];
for (int i = 0; i < n; i++) {
     perm[i] = i;
}

for (int i = 0; i < n; i++) {
    int new_place = (int) (Math.random()*n); // Exchange element with any random element.
    int temp = perm[new_place];
    perm[new_place] = perm[i];
    perm[i] = temp;
}

Но в книге рандомизирующий код написан как (только изменения в цикле for):

      for (int i = 0; i < n; i++) {
    int new_place = i + (int) (Math.random() * (n-i)); // Exchange element with a random element to its right.
    int temp = perm[new_place];
    perm[new_place] = perm[i];
    perm[i] = temp;
}

и они говорят, что с помощью кода, который они пишут, они гарантируют, что тасование будет случайным, равномерно выбирая из карт, которые еще не выбраны. (В отличие от моего подхода, когда я выбираю из всех карт).(Я считаю, что они написали модифицированную версию алгоритма Фишера-Йейтса).

Я просто хочу знать, является ли мой код (приведенный выше) также беспристрастным для генерации случайных чисел или нет? Если да, то почему? Если нет, то почему?

(Первые 2 комментария относятся к вопросу, который я задал, правильно ли то, что я делаю, для генерации случайных чисел, но я хотел спросить, беспристрастно ли это. Но тогда я не знал этого термина, извините. Относительно текущего вопроса , 4-й комментарий имеет очень хорошую ссылку для понимания).

Answer 1

Ваш код, похоже, имеет предвзятость в распределении сгенерированного массива. Результаты 6000 статистики для n = 3 следующие.

      static int[] shuffle(int n) {
    int[] perm = IntStream.range(0, n).toArray();
    for (int i = 0; i < n; i++) {
        int new_place = (int) (Math.random()*n);
        int temp = perm[new_place];
        perm[new_place] = perm[i];
        perm[i] = temp;
    }
    return perm;
}

static final Comparator<int[]> INT_ARRAY_COMPARATOR = (a, b) -> Arrays.compare(a, b);

public static void main(String[] args) {
    Map<int[], Integer> counts = new TreeMap<>(INT_ARRAY_COMPARATOR);
    int n = 3;
    for (int i = 0; i < 6000; ++i)
        counts.compute(shuffle(n), (k, v) -> v == null ? 1 : v + 1);
    counts.entrySet()
        .forEach(e -> System.out.println(Arrays.toString(e.getKey()) + "=" + e.getValue()));
}

выход:

      [0, 1, 2]=865
[0, 2, 1]=1113
[1, 0, 2]=1161
[1, 2, 0]=1093
[2, 0, 1]=873
[2, 1, 0]=895

[0, 1, 2] и [2, 1, 0] кажутся нечастыми.

При выполнении с кодом книги это делается следующим образом.

      static int[] shuffle(int n) {
    int[] perm = IntStream.range(0, n).toArray();
    for (int i = 0; i < n; i++) {
        int new_place = i + (int) (Math.random() * (n-i));
        int temp = perm[new_place];
        perm[new_place] = perm[i];
        perm[i] = temp;
    }
    return perm;
}

выход:

      [0, 1, 2]=987
[0, 2, 1]=978
[1, 0, 2]=1014
[1, 2, 0]=994
[2, 0, 1]=1041
[2, 1, 0]=986

Я не могу объяснить, почему это так, но вы должны попробовать.