Перемешивать элементы массива / n чисел равномерно случайным образом. Возможно в ожидаемое время O (n)

Question

Возможно ли перетасовать элементы массива n-размера равномерно, то есть вероятность любого из n! Комбинации происходят одинаково, в ожидаемое время O(n). Как так? Я должен перетасовать элементы A в новый массив B Первое, что приходит мне в голову, когда я пытаюсь это сделать, это просто выбрать случайное число i от 1 до n, посмотреть, было ли выбрано A[i], если да, то повторить, в противном случае поставить A[i] в первой доступной позиции в B. Однако эта проблема со сборщиком купонов ожидала времени O(n log n). Может кто-нибудь предложить O(n) алгоритм ожидаемого времени.

Спасибо.

Answer 1

Вы должны посмотреть на Фишера-Йейтса shuffle.

Из статьи:

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

Так что это соответствует вашим требованиям. Это тоже довольно легко реализовать.

Answer 2

То, что вы хотите, это случайная выборка из набора , которая выбирает каждый элемент с равной вероятностью.

Answer 3

Для каждой позиции массива:

Выберите случайное число от текущей позиции до конца массива

Обмен текущей позиции со случайной позицией

Это должно дать вам O (n) без задачи поиска неиспользуемой позиции массива Это предполагает, что вы можете использовать своп на месте и вам не нужно создавать новый массив.