c++ - 来自两个列表的随机对

Question

我的问题类似于this一个。

我有两个列表:包含 n 元素的 X 和包含 m 元素的 Y - 假设它们包含n x m 矩阵 A 的行和列索引。现在，我想在矩阵 A 中的 k 随机位置写入一些内容。

我想到了两个解决方案:

1. 从X 中获取一个随机元素x，从Y 中获取一个随机元素y。检查是否已将某些内容写入 A[x][y]，如果没有 - 写入。但是如果 k 接近于 m*n 我可以永远这样射击。
2. 创建一个包含所有可能的索引组合的 m*n 数组，将其打乱，绘制前 k 元素并写入其中。但是我在这里看到的问题是，如果n和m都很大，那么新创建的n*m数组可能是巨大的(洗牌也可能需要一些时间)。
3. Karoly Horvath 建议将两者结合起来。我想我必须选择阈值 t 和:

.

if( k/(m*n) > t ){
    use option 2.
}else{
    use option 1.
}

关于如何选择 t 有什么建议吗？

还有我错过的其他(更好的)方法吗？

Answer 1

有一个 elegant algorithm由于弗洛伊德(Floyd)用于从整数范围内进行无放回抽样。您可以通过 C++ 函数将 [0, n*m) 中的结果整数映射到坐标 [m](int i) { return std::make_pair(i/m, i %米)； 。