Перемешивание массива в Java с использованием Random.nextInt два раза

Question

Является ли массив целых чисел правильно перетасованным при использовании Random.nextInt два раза для замены двух значений?

Пример кода:

Random rand = new Random(); 
    for (int i = 0; i < values.length; i++) { 
     nIndexOld = rand.nextInt(values.length); 
     nIndexNew = rand.nextInt(values.length); 

     nTempValue = values[nIndexOld]; 
     values[nIndexOld] = values[nIndexNew]; 
     values[nIndexNew] = nTempValue; 
    } 

Answer 1

Лучше ограничение nextInt до размера входящего массива

Random rand = new Random(); 
for (int i = 0; i < values.length; i++) { 
    nIndexOld = rand.nextInt(values.length); 
    nIndexNew = rand.nextInt(values.length); 

    nTempValue = values[nIndexOld]; 
    values[nIndexOld] = values[nIndexNew]; 
    values[nIndexNew] = nTempValue; 
} 

Answer 2

Если в вашем примере

values.length = 40 

Тогда да массив действительно перемешиваются правильно ,

Answer 3

Нет, ваш алгоритм не может дать однородное распределение возможных перестановок. Смотрите объяснение подобной ошибки в разделе "Implementation errors":

Это можно видеть из того, что делать это дает п ^п различные возможные последовательности свопы, а есть только п! возможно перестановки n-элементной матрицы ...

Ваш случай немного отличается, но может применяться одна и та же логика. На каждом шаге итерации вы генерируете два randoms (0...n-1), поэтому есть n * n возможные изменения массива, которые могут быть применены. Вы делаете это n раз. Таким образом, общее количество путей, с которыми вы можете пойти с равной вероятностью, равно (n * n)n, но есть n! возможных перестановок.

Например, у вас есть три элемента. На каждом шаге есть 3 * 3 = 9 способы изменения текущего состояния. Выполнение этого три раза дает 9 * 9 * 9 = 729 возможные способы изменения начального массива. Было бы идеально иметь равное количество всех возможных перестановок в этом наборе. Однако есть 3! = 6 возможные разные конечные результаты. Число сгенерированных перестановок 729 не делится на 6. Поэтому наверняка некоторые перестановки имеют более высокую вероятность выбора.

Для собственных Java реализаций современной версии перетасовки Fisher-Yates см, например Random shuffling of an array