假设我们要从总大小为 n
的集合中随机选择一个大小为 m
的子集。由于总集中的每个元素都可以使用 S = {0, 1, 2, ..., (n - 1)}
中的唯一索引来标识。该问题等同于从 S
中随机选择 m
个不同的元素。
一个简单的算法会重复调用伪随机数生成器 rand
以从 S
生成随机数。如果之前已经生成过数字,请重试。算法终止,直到生成 m
个不同的数字。此算法的最佳空间复杂度为 O(1)
,但可能会调用 rand
超过 m
次。
我更关心时间复杂度而不是空间复杂度,如果合理的话,我很乐意用空间换取时间。所以我实现了以下算法。它调用 rand
恰好 min{m, (n - m)}
次,但代价是增加了 O(n)
的空间复杂度>。 (原代码可见here)
template <typename Clock = std::chrono::high_resolution_clock>
auto tick_count() {
return Clock::now().time_since_epoch().count();
}
template <typename OutIt, typename RAND = std::minstd_rand,
typename Uint = typename RAND::result_type>
void random_subset(std::size_t m, std::size_t n, OutIt it, RAND&& rand =
RAND(static_cast<Uint>(tick_count()))) {
assert(n - 1 <= rand.max());
assert(m <= n);
if (m == 0) return;
auto swapped = false;
auto tmp = n - m;
if (tmp < m) {
m = tmp;
swapped = true;
}
std::vector<std::size_t> indices(n);
std::iota(indices.begin(), indices.end(), static_cast<std::size_t>(0));
auto back_it = indices.end();
for (std::size_t i = 0; i < m; ++i) {
auto idx = rand() % (n - i);
std::swap(indices[idx], *--back_it);
}
swapped ? std::copy(indices.begin(), back_it, it) :
std::copy(back_it, indices.end(), it);
}
我想知道算法是否可以在性能方面进一步改进。也欢迎对通用实现进行改进。
最佳答案
也许您可以使用 Fisher-Yates algorithm 的一个非常小的变体用于随机洗牌,特别是 second variant of the Durstendfeld version :
-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
j ← random integer such that 0 ≤ j < n-i
exchange a[i] and a[i+j]
只需将循环终止从 n - 2 更改为您需要的。
在证明中,循环不变量是一旦传递了一个索引i,到它的数组就是一个随机洗牌。因此,您可以提前终止并获得所需的结果。
关于c++ - 选择随机子集的通用算法实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35101370/