一种从数组中采样非重复随机元素的有效算法

Question

我正在寻找一种从给定数组中挑选m个随机元素的算法。先决条件是：

• 采样元素必须是唯一的
• 要从中采样的阵列可以包含重复
• 不一定要对要从中采样的数组进行排序

这就是我设法想出的。在这里，我还假设数组中唯一元素的数量大于(或等于(m。

#include <random>
#include <vector>
#include <algorithm>
#include <iostream>

const std::vector<int> sample(const std::vector<int>& input, size_t n) {
std::random_device rd;
std::mt19937 engine(rd());
std::uniform_int_distribution<int> dist(0, input.size() - 1);

std::vector<int> result;
result.reserve(n);
size_t id;
do {
id = dist(engine);
if (std::find(result.begin(), result.end(), input[id]) == result.end())
result.push_back(input[id]);
} while (result.size() < n);
return result;
}

int main() {
std::vector<int> input{0, 0, 1, 1, 2, 2, 3, 3, 4, 4};
std::vector<int> result = sample(input, 3);
for (const auto& item : result)
std::cout << item << ' ';
std::cout << std::endl;
}

这种算法似乎不是最好的。有没有一种更高效(时间复杂度更低(的算法来解决这项任务？如果该算法还可以断言输入阵列中的唯一元素的数量不小于M(或者如果不是这样，则选择尽可能多的唯一元素(，那将是好的。

可能的解决方案

正如MSchanges所建议的，我使用std::unordered_set来去除重复项，使用std::shuffle来打乱由集合构建的向量中的元素。然后我调整矢量大小并返回。

const std::vector<int> sample(const std::vector<int>& input, size_t M) {
std::unordered_set<int> rem_dups(input.begin(), input.end());
if (rem_dups.size() < M) M = rem_dups.size();

std::vector<int> result(rem_dups.begin(), rem_dups.end());
std::mt19937 g(std::random_device{}());
std::shuffle(result.begin(), result.end(), g);
result.resize(M);
return result;
}

Answer 1

注释已经注意到std::set的使用。在输入中检查M个唯一元素的额外请求使这变得有点复杂。这里有一个替代实现：

1. 将所有输入放入std::set或std::unordered_set中。这将删除重复项
2. 将所有元素复制到返回向量
3. 如果它具有M个以上的元素，则std::shuffle为其，resize为M个元素
4. 归还

Answer 2

使用集合S来存储输出，最初为空。

i = 0
while |S| < M  && i <= n-1
swap the i'th element of the input with a random greater element
add the newly swapped i'th element to your set if it isn't already there
i++

这将以S具有来自输入数组的M个不同元素(如果有M个不同的元素(结束。然而，在输入数组中更常见的元素更有可能在S中(除非您首先完成从输入中消除重复项的额外工作(。