algorithm - 具有大量重复的无偏洗牌

Question

Fisher-Yates 算法生成有限序列的无偏随机排列。运行时间与被洗牌的元素数量成正比。

我想用大量零元素来洗牌一些非零元素。

使用列表实现 Fisher-Yates 算法会导致洗牌过程花费太长时间并且需要太多存储空间。Fisher--Yates 算法中的大多数步骤将简单地切换重复零元素的位置。

是否存在随机洗牌（或替代）算法：

1. 导致无偏排列
2. 不需要洗牌和存储所有重复的元素

Answer 1

由于 Fisher-Yates shuffle 产生随机排列，因此它的逆也是随机排列：

1. 对于 i=1 到 n-1：
   1. 在 [0,i] 中选择一个随机数 j
   2. 交换元素 i 和 j

但是，在这个算法中，如果你有 m 个非零元素，并且你从所有这些元素开始，那么第一个 nm 迭代保证会交换零，所以你可以跳过那些。

如果要避免存储所有零元素，请使用哈希映射而不是数组。