c++ - 从数组中抽取非重复随机元素的有效算法

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(或者如果不是这种情况，则选择尽可能多的唯一元素)。

可能的解决方案

正如 MSalters 所建议的，我使用 std::unordered_set 来删除重复项，并使用 std::shuffle 来打乱从集合构造的 vector 中的元素。然后我调整 vector 的大小并将其返回。

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. 将所有元素复制到返回 vector
3. 如果它有超过 M 个元素，std::shuffle 并将它resize 为 M 个元素。
4. 归还它。