algorithm - 大量重复的无偏洗牌

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 次迭代一定会交换零，因此您可以跳过这些元素。

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