algorithm - 从网格中随机选择一个单元格并标记直到出现某种情况

Question

我有 NxN bool 矩阵，它的所有元素都有初始状态 false

bool[][] matrix = GetMatrix(N);

在循环的每一步中，我想在所有false单元格中均匀地随机选择一个单元格(第i行，第j列)，并将其设置为true 直到某些情况发生。

使用哪种方法？我想到了这两种方式。

• 从 0...(NxN-1) 创建一个 NxN 数组，使用均匀洗牌算法洗牌，然后依次从该数组中取出 i 元素并设置矩阵[i/N][i%N].

使用 O(N^2) 额外内存，初始化花费 O(N^2) 时间

第二个

• 从 0...(N^2-1) 生成随机 i，如果矩阵中设置了 (i/N, i%N)，则重复随机生成直到创建未设置的元素。

这种方式不使用任何额外的内存，但我很难估计性能......是否可以这样，当设置了除一个元素之外的所有元素时，随机重复很多次寻找空闲单元格？我是对的吗，只要随机在理论上一致，这种情况就不会经常发生吗？

Answer 1

我将尝试回答您的问题，最坏的情况分析发生在，正如您所指出的，除了一个单元格之外的所有单元格都被占用。

让我们首先注意 p = P(X = m) = 1/N^2 。由此，我们得出您必须等待 k 次才能获得所需结果的概率为 P( Y = k) = p * (1-p)^(k -1) 。这意味着，对于 N = 10，您需要 67 个随机数才能有大于 50% 的概率获得您的随机数，而 457 个随机数有大于 99% 的概率。

给出大于 alpha 的概率所需的 k 次抛掷次数的通用公式是:

k > (log(1 - alpha) / log(1-p)) -1

其中p定义如上，等于1/N^2

随着 N 变大，情况可能会变得更糟。您可以考虑创建一个您需要的索引列表，并为其随机获取一个。