Правильность изменения порядка Knuth

Question

Я занимаюсь программированием на Java, и я написал этот код, посмотрев псевдокод на странице Википедии. Первый, упомянутый ниже подзаголовка «Современный алгоритм», мне было просто любопытно, работает ли мой алгоритм, что он должен делать, и делаю это правильно, а если нет, я не могу узнать, где моя ошибка. Надеясь, что кто-нибудь из вас, ребята, поможет мне разобраться. Спасибо. Вот пример кода:

public class KnuthShuffle { 


public static void main(String args[]) { 
    int n; 
    Scanner s = new Scanner(System.in); 
    System.out.println("Enter length of array: "); 
    n = s.nextInt(); 
    ArrayList<Integer> a = new ArrayList<Integer>(); 
    for (int i=0;i<n;i++){ 
     a.add(i); 
    } 
     System.out.println("Pre shuffle: "+a); 
     Random r = new Random(); 


    for(int k=n-1;k>1;k--){ 
     int j = r.nextInt(k)+0; 
     Collections.swap(a, j, k); 

    } 
    System.out.println("Post shuffle: "+a); 
} 
} 

и вот ссылка на страницу Википедии я имел в виду. Knuth Shuffle. Кроме того, хотя я понимаю, что массив перетасовывается, не просматривая объяснения в математической строгости, я не могу сразу увидеть правильность алгоритма. Если бы кто-нибудь мог освежить это, это было бы потрясающе! Спасибо заранее.

Answer 1

Как уже указывалось, аргумент r.nextInt() в вашем коде должен быть k+1 вместо k. Это связано с тем, что according to the documentation метод nextInt() возвращает равномерно распределенное неотрицательное случайное целое число менее его аргумент.

В принципе, вместо перетасовки Кнута, вы случайно (почти, из-за другую ошибку, описанной ниже) реализованы Sattolo's algorithm для генерации случайных циклических перестановок.

В самом деле, ваш алгоритм также имеет другую ошибку, которую я нашел во время написания этого ответа: так как индексы массива Java начинаются с нуля, условие завершения для for петли должно быть n > 0, не n > 1. Неправильное условие заставляет ваш код пропускать последнюю итерацию, так что даже при первой исправленной ошибке он все равно не генерирует все возможные перестановки.

---

Полезный способ проверить правильность своей реализации в случайном порядке, чтобы запустить его много раз на небольшой массив, скажем, три или четыре элементов, где число возможных перестановок по-прежнему разумно (3 ×- × 1 = 6 для трех элементов, 4 1 = 24 для четырех элементов) и убедитесь, что каждая перестановка производится примерно одинаково часто.

Например, если вы run your code 10,000 times on a three-element array и напечатать количество раз генерируется каждая перестановка, вы получите что-то вроде этого:

[2, 1, 0]: 5006 
[0, 2, 1]: 4994 

ОК, так что цифры выглядят примерно равны, что составляет неизбежное случайная вариация. Но ждать! Почему код только производит две перестановки из возможных шести ?!

Ну, это одна из ошибок в вашем звонке r.nextInt(), о котором я упоминал выше. Let's fix it and try again:

[0, 1, 2]: 3317 
[2, 1, 0]: 3344 
[0, 2, 1]: 3339 

Мм, это не так хорошо. Конечно, цифры все еще довольно четкие, и, конечно, три ближе к шести, чем к двум, но мы определенно еще не там.

О, верно, была и другая ошибка. Let's fix that one too, and see what happens:

[0, 1, 2]: 1727 
[1, 2, 0]: 1633 
[2, 1, 0]: 1621 
[0, 2, 1]: 1667 
[2, 0, 1]: 1643 
[1, 0, 2]: 1709 

Ах, намного лучше! Мы получаем все шесть возможных перестановок и примерно в равных количествах. Хорошо, таким образом, может быть, мы немного беспокоюсь о разнице между 1727 и 1621, так что давайте increase the iteration count to 100,000 and try again:

[0, 1, 2]: 16590 
[1, 2, 0]: 16750 
[2, 1, 0]: 16738 
[2, 0, 1]: 16654 
[0, 2, 1]: 16425 
[1, 0, 2]: 16843 

Да, это выглядит довольно хорошо.

В самом деле, в рандомизированных экспериментах, как это, отсчеты результат примерно Poisson-distributed, поэтому standard deviation (который, грубо говоря, равно ожидаемое количество случайных изменений в отсчетов) приблизительно равна корню квадратному из ожидаемого сосчитать. Здесь мы ожидаем около 16,667 экземпляров каждой перестановки, поэтому стандартное отклонение составляет около 129. Наибольшее наблюдаемое отклонение 16,667 − 16,425 = 242 меньше, чем вдвое больше, поэтому мы все еще находимся в пределах 95% confidence interval.

(Точнее, выходы в тесте, подобные этому, на самом деле являются multinomially distributed, поэтому, чтобы получить правильное стандартное отклонение, мы должны умножить счетчик ожиданий на один минус вероятность результата (т. Е. Ожидаемое количество событий/общее количество испытаний), прежде чем принимать квадратный корень. В этом случае с шестью одинаково вероятными результатами правильное стандартное отклонение составляет sqrt (100 000 × 1/6 × (1 − 1/6)) & приблизительно 118, что немного меньше 129, приведенный в приближении Пуассона. Эта коррекция слегка отклоняет наблюдаемое отклонение от 95% доверительного интервала, но не настолько, поэтому мы все еще можем быть достаточно уверены в том, что вариация является случайной. В конце концов, события с 5% вероятность случится примерно раз в двадцать испытаний (и для этой цели каждый из шести puts считается пробным).

Answer 2

Я думаю, что ваш цикл воспроизведения в случайном порядке должен быть так:

for(int k=n-1;k>=1;k--){ 
    int j = r.nextInt(k+1); 
    Collections.swap(a, j, k); 
} 

Это будет следовать описанию алгоритма, к которому вы связаны между собой. Вам нужно изменить условие завершения цикла, чтобы перетасовать случай 0,1, где k = 1. Вам нужно изменить параметр nextInt, чтобы вы получили j < = k, как указано в алгоритме.

Answer 3

Неверная реализация. Легкий способ проверить правильность тасования - это выяснить случайные вызовы. Например, при правильной перетасовке 5 вещей вам нужно будет выбрать один из пяти, затем один из четырех, затем один из трех ... и т. Д.

в цикле:

for(int k=n-1; k>1; k--) { 
    int j = r.nextInt(k) + 0; 
    ... 

Первый вызов nextInt (к) будет возвращать значение от 0 до N-2: п-1 аргумент является эксклюзивным связаны. Таким образом, вы начинаете перетасовывать 5 объектов, выбирая один из четырех.