无冲突随机填充数组的算法

Question

假设我将一个包含 N 个整数的数组设置为值“0”，我想从该数组中选择一个值为“0”的随机元素并将其设为值“1”

我如何有效地做到这一点？

我想出了 2 个解决方案，但它们看起来很低效

第一个解决方案

int array[N] //init to 0s
int n //number of 1s we want to add to the array
int i = 0
while i < n
    int a = random(0, N)
    if array[a] == 0
        array[a] = 1
        i++
    end if
end while

由于存在碰撞概率，对于大型数组来说效率极低

第二个涉及一个包含所有剩余 0 位置的列表，我们选择一个介于 0 和剩余 0 的数量之间的随机数来查找列表中与数组中的索引对应的值。它比第一个解决方案可靠得多，因为操作的数量是有限的，但如果我们想完全填充数组，最坏情况下的复杂度仍然是 N²

Answer 1

您可以用 n 个 1 和 N-n 个零填充数组并进行随机洗牌。

Fisher-Yates shuffle 具有线性复杂度：

for i from N−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Answer 2

您的第二个解决方案实际上是一个好的开始。我假设它涉及在每次更改后重建位置列表，如果您想填充整个数组，这将使其成为 O(N²)。但是，您不需要每次都重建列表。既然你想填充数组，你可以使用随机顺序并相应地选择剩余的位置。

例如，采用以下数组（大小为 7 且最初未全为零）：[0, 0, 1, 0, 1, 1, 0]

在此处 [0, 1, 3, 6] 构建零位置列表后，只需将其打乱即可获得随机排序。然后按照位置给出的顺序填充数组。

例如，如果随机播放给出 [3, 1, 6, 0]，那么您可以像这样填充数组：

[0, 0, 1, 0, 1, 1, 0]  <- initial configuration
[0, 0, 1, 1, 1, 1, 0]  <- First, position 3
[0, 1, 1, 1, 1, 1, 0]  <- Second, position 1
[0, 1, 1, 1, 1, 1, 1]  <- etc.
[1, 1, 1, 1, 1, 1, 1]

如果数组最初是用零填充的，那就更容易了。您的初始列表是从 0 到 N（数组的大小）的整数列表。洗牌并应用相同的过程。

如果你不想填满整个数组，你仍然需要构建整个列表，但你可以在洗牌后截断它（这意味着在某个点后停止填充数组）。

当然，这个解决方案要求数组在每一步之间不发生变化。

无冲突随机填充数组的算法

Algorithm to fill an array randomly without collision

arrays

algorithm

random-access

fill