大量重复的无偏洗牌

Question

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

我想用大量的零元素打乱一些非零元素。

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

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

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

Answer 1

由于 Fisher-Yates 随机排列产生随机排列，其逆排列也是随机排列：

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

但是，在这个算法中，如果你有 m 个非零元素，并且你从最后所有的元素开始，那么前 n-m 次迭代保证交换零，所以你可以跳过那些。

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