Беспристрастная перетасовка с большим количеством дубликатов

Question

Алгоритм Фишера – Йейтса генерирует несмещенные случайные перестановки конечной последовательности. Время работы пропорционально количеству перемешиваемых элементов.

Я хочу перемешать несколько ненулевых элементов с большим количеством нулевых элементов.

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

Существует ли алгоритм случайного перемешивания (или альтернативный), который:

1. Приводит к беспристрастным перестановкам
2. Не требует перетасовки и хранения всех повторяющихся элементов

Answer 1

Поскольку тасование Фишера-Йетса производит случайную перестановку, его обратная перестановка также является случайной перестановкой:

1. Для i = от 1 до n-1:
   1. выберите случайное число j в [0, i]
   2. поменять местами элементы i и j

Однако в этом алгоритме, если у вас есть m ненулевых элементов, и вы начинаете со всеми из них в конце, то первые нм итерации гарантированно заменяют нули местами, поэтому вы можете просто пропустить их.

Используйте хэш-карту вместо массива, если вы не хотите хранить все нулевые элементы.