Анализ алгоритма перетасовки

Ответ 1

Самое простое доказательство того, что этот алгоритм не дает равномерно случайной перестановки

for (int i = 0; i < 3; ++i) {
   swap(a[i], a[rand() % 3]);
}

Это то, что он генерирует 27 возможных результатов, но есть только 3!= 6 перестановок. Поскольку 6 не делит 27, должна быть какая-то перестановка, которая выбрана слишком много, а некоторые из них немного подобраны.

Почему оптимальный алгоритм O (n)? Ну, случайная перетасовка иногда должна касаться каждого входа (чтобы изменить их), поэтому любой оптимальный алгоритм должен выполнять по крайней мере O (n) работу.

Почему алгоритм Кнута исправлен? Это требует немного более глубокого понимания. Вы можете доказать с помощью индукции, что первый элемент выбран с правильной вероятностью (каждый элемент в равной степени может быть первым), а затем докажите, что шаг индукции выполняется по мере продвижения по циклу, что второй, третий и т.д. Элементы также выбирается с правильной вероятностью из остальных частей массива.

Ответ 2

Рассмотрим список трех элементов. Он имеет эти возможные состояния и связанные вероятности:

1 [a, b, c] (0)

В первой операции перетасовки a имеет 1/3 вероятность замены любого из элементов, поэтому возможные состояния и связанные с ними вероятности следующие:

From (0)
1/3 [a, b, c] (1)
1/3 [b, a, c] (2)
1/3 [c, b, a] (3)

Во второй операции перетасовки происходит то же самое, что и во втором слоте, поэтому:

From (1) ([a, b, c])
1/9 [b, a, c] (4)
1/9 [a, b, c] (5)
1/9 [a, c, b] (6)
From (2) ([b, a, c])
1/9 [a, b, c] (7)
1/9 [b, a, c] (8) 
1/9 [b, c, a] (9)
From (3) ([c, b, a])
1/9 [b, c, a] (10)
1/9 [c, b, a] (11)
1/9 [c, a, b] (12)

В третьей операции перетасовки происходит то же самое, за исключением третьего слота, поэтому:

From (4) ([b, a, c])
1/27 [c, a, b] (13)
1/27 [b, c, a] (14)
1/27 [b, a, c] (15)
From (5) ([a, b, c])
1/27 [c, b, a] (16)
1/27 [a, c, b] (17)
1/27 [a, b, c] (18)
From (6) ([a, c, b])
1/27 [b, c, a] (19)
1/27 [a, b, c] (20)
1/27 [a, c, b] (21)
From (7) ([a, b, c])    
1/27 [c, b, a] (22)
1/27 [a, c, b] (23)
1/27 [a, b, c] (24)
From (8) ([b, a, c])
1/27 [c, a, b] (25)
1/27 [b, c, a] (26)
1/27 [b, a, c] (27)
From (9) ([b, c, a])
1/27 [a, c, b] (28)
1/27 [b, a, c] (29)
1/27 [b, c, a] (30)
From (10) ([b, c, a])
1/27 [a, c, b] (31)
1/27 [b, a, c] (32)
1/27 [b, c, a] (33)
From (11) ([c, b, a])
1/27 [a, b, c] (34)
1/27 [c, a, b] (35)
1/27 [c, b, a] (36)
From (12) ([c, a, b])
1/27 [b, a, c] (37)
1/27 [c, b, a] (38)
1/27 [c, a, b] (39)

Объединяя похожие выражения, получаем:

4/27 [a, b, c] From (18), (20), (24), (34)
6/27 [a, c, b] From (17), (21), (23), (23), (28), (31)
5/27 [b, a, c] From (15), (27), (29), (32), (37)
5/27 [b, c, a] From (14), (19), (26), (30), (33)
4/27 [c, a, b] From (13), (25), (35), (39)
3/27 [c, b, a] From (16), (36), (38)

Это явно неравномерно.

Перетасовка, в которой вы выбираете только элементы, которые еще не были выбраны, верна. Для доказательства я представляю это:

У вас есть мешок с элементами. Если вы случайно выбрали из этого мешка и поместите результирующие элементы в список, вы получите случайный список. Это, по сути, то, что происходит с заменой только тех элементов, которые еще не были выбраны. (Рассмотрим список, в котором вы помещаете материал в начало списка, а сумка - хвостом списка, который можно поменять местами).

Ответ 3

Во-первых, не совсем верно, что описанный алгоритм O (n), хотя он довольно близок. Это действительно должно быть O (n * log (n)).

Вот почему: первая свопа требует рисования из n элементов, затем n-1... 2. Но сложность выбора из n элементов должна быть действительно log (n), потому что вам нужно генерировать log (n) random биты.

rrenaud дает хороший аргумент, что "плохой" алгоритм не является однородным, поэтому я попытаюсь утверждать, что "хороший" алгоритм является однородным. Каждый шаг вы выбираете из n, n-1,... 1 вариантов, так что в конечном итоге есть n! выбор, который вы могли бы сделать. Поскольку есть n! способы упорядочения списка, если каждая договоренность может быть достигнута, по крайней мере, одной последовательностью выборов, тогда каждая договоренность может быть достигнута ровно одной последовательностью выборов. Таким образом, чтобы показать, что он является однородным, нам нужно только показать, что при некотором возможном упорядочении мы можем достичь его с помощью последовательности выборов.

Теперь проблема выглядит просто. Скажем, вы начинаете с

a b c d e

И вы хотите получить

b c d e a

Наведите курсор на 0-й элемент. С чем вы должны поменяться? b, потому что вы хотите переместить его в позицию 0. Теперь прогресс. На каждом шаге все элементы "позади" вы находитесь в нужном месте, поэтому, когда вы дойдете до конца, все элементы находятся в нужном месте.

Ответ 4

Прежде всего, обратите внимание, что путь Кнута должен быть равномерно случайным, так как это по существу эквивалентно рисованию случайных карт из стека А и формированию стека В путем их укладки в случайном порядке. Это должно быть равномерно случайным.

Чтобы увидеть, что другой способ плох, достаточно показать, что число отдельных результатов исключает возможность получения однородного результата. Существует 52 ^ 52 способа выбрать 52 случайных числа от 1 до 52. Однако есть 52! перестановки этих целых чисел. 52! имеет 47 как фактор, тогда как 52 ^ 52 нет; так что 52! Не равномерно разделяет 52 ^ 52. это означает, что по крайней мере одна перестановка имеет больше результатов, которые приводят к ней, чем какая-либо другая перестановка... чтобы увидеть это, попробуйте равномерно делить результаты, пока не закончите. Так как количество результатов не кратно количеству перестановок, вы не можете дать всем одну и ту же сумму. Другими словами, вы не можете равномерно разделить 12 присосок на 5 детей, если вы отпустите всех присосок. Тот же принцип.