在2d数组中生成/放置k个随机项 [英] Generating/Placing k random items in a 2d array

问题描述

我有一个二维数组，一种矩阵(m x n).我需要在 k 个单元格中生成"1"，但是每个单元格的概率应该相等.

I have a 2d array, matrix of a sort (m x n). I need to generate '1' in k cells, but the probability of it should be equal for each cell.

例如，如果k = 3，我们随机选择 放置3个1的位置:

for example, if k=3, we pick randomly where to place the 3 '1's :

[0，0，0，0]

[0, 0, 0, 0]

[0，1，1，0]

[0, 1, 1, 0]

[1、0、0、0]

[1, 0, 0, 0]

首先，我通过生成一个模数为m * n(行*列)的随机数来解决这个问题. 但是，这意味着从理论上讲，我们可以生成矩阵的末尾而无需生成单个"1".

At first, I tackled this by generating a Random of modulu m * n (rows * columns). But, that means that we could theoretically get to the end of the matrix without generating a single '1'.

然后，我读到有关 Yates Shuffle 的信息，但不确定用它实现它是否明智甚至可行.

Then, I read about Yates Shuffle, but wasn't sure whether that's wise and even feasible to implement it with that.

实现此目的的有效方法是什么?

What is an efficient way to implement this?

推荐答案

这本质上是无替换采样"的问题:在 mn 个单元格中，选择 k 其中没有更换.有许多方法可以解决此问题，具体取决于 mn 与 k 的大小有关.如果 mn 相对较小，则Fisher– Yates混洗效果很好；反之亦然.列出一个单元格列表，将它们随机排列，然后将前 k 个单元格设置为1.

This is essentially a problem of "sampling without replacement": Out of mn cells, choose k of them without replacement. There are many approaches to this problem, depending on how big mn is in relation to k. If mn is relatively small, then a Fisher–Yates shuffle will work well; make a list of cells, shuffle them, then take the first k cells to set to 1.

有关更多详细信息，请参阅我的无替换采样和改组. (我的评论的一部分移至此处:)不同的采样算法在时间和空间方面具有不同的权衡.例如，费舍尔·耶茨混洗的时间和空间复杂度为O(mn)，而部分混洗的时间和空间复杂度为O(k).

For more details, see my sections on sampling without replacement and shuffling. (Part of my comment moved here:) Different sampling algorithms have different tradeoffs in terms of time and space. For example, a Fisher–Yates shuffle has time and space complexity of O(mn), while a partial shuffle can have time complexity O(k).

这篇关于在2d数组中生成/放置k个随机项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！