从包含n个元素的向量中随机选择m个元素

Question

我有一个包含 n 个元素的向量。我需要从向量中随机选择一个不重复的子集，该子集包含 m 个元素。最有效的方法是什么？在我的代码中需要执行数千次。

我想到的解决方案是使用 rand() 生成一个介于 0 和 n 之间的随机数 k。然后选择向量中的第 k 个元素，并将其插入到一个 std::set 中。重复这个步骤直到集合的大小等于 m。我现在可以确信，集合包含了从 n 个元素的集合中随机选择的 m 个唯一元素。

还有哪些可能的解决方案？

谢谢。

- Vinay

---

在向量上使用std::random_shuffle()，然后取出前m个元素，怎么样？ - jrok

@jrok：虽然简单，但当m远小于n时，这种方法非常低效。 - Mooing Duck

可能是选择单个随机值组合的算法？的重复问题。 - Jerry Coffin

@MooingDuck 但事实上，std::random_shuffle()只是一个完全置换，它还使用了Fisher-Yates shuffle。请参阅cppreference中的可能实现的第一个版本。对于那些想要理解被接受的答案以及std::random_shuffle()的人来说，这值得一读。 - Rick

@Rick：当然，这是相同的算法，但是它不是在处理m个元素后停止，而是对整个数据集进行操作，这是一种巨大的时间浪费。这就是std::sort和std::partial_sort之间的区别。 - Mooing Duck

Answer 1

你想要一个 Fisher-Yates shuffle（在 M 次迭代后停止）：

template<class BidiIter >
BidiIter random_unique(BidiIter begin, BidiIter end, size_t num_random) {
    size_t left = std::distance(begin, end);
    while (num_random--) {
        BidiIter r = begin;
        std::advance(r, rand()%left);
        std::swap(*begin, *r);
        ++begin;
        --left;
    }
    return begin;
}

演示请见http://ideone.com/3A3cv。当你只需要从集合中获取少量的随机数时，这比std::random_shuffle快得多，并且即使N==M，速度也应该基本相同。

- Michael Burr

---

@Burr 谢谢！我有一个包含一百万个元素的向量，我需要随机选择其中的100个元素。这正是我正在寻找的。 - Vinay

rand()：请参见http://codereview.stackexchange.com/questions/39001/fisher-yates-modern-shuffle-algorithm。该链接介绍了现代化的Fisher-Yates洗牌算法。 - dani

嗯..这是一个“选择x次后停止”的std::random_shuffle版本。我很好奇STL为什么没有重载这个版本。顺便说一句，谢谢:D。 - Rick

Answer 2

您可以采用的一种方法是创建一个向量的所有索引列表，对它们进行洗牌，然后取前n个作为所选对象的索引：

struct rangegenerator {
    rangegenerator(int init) : start(init) { }

    int operator()() {
        return start++;
    }

    int start;
};

vector<T> numbers; // this is filled somewhere else

vector<int> indices(numbers.size());

generate(begin(indices), end(indices), rangegenerator(0));

random_shuffle(begin(indices), end(indices));

// then take the first n elements of indices and use them as indices into numbers

- Seth Carnegie

---

当 m 远小于 n 时，这种方法效率非常低下。对于所有 m（其中 m 小于 n），很容易想出比这种方法更快的答案。 - Mooing Duck

@Seth: 不得不同意Moo的观点。这可能是完成给定任务最糟糕的方法之一，不确定为什么OP将其标记为答案。正确的答案显然是Burr的答案。 - Jared Krumsie

@JaredKrumsie，原帖要求“其他可能的解决方案”，我写的绝对是一个可能的解决方案。唯一不正确的回答是根本不起作用的回答。 - Seth Carnegie

Answer 3

自从 C++20 开始，我们可以使用 std::ranges::sample()：

#include <cassert>
#include <iostream>
#include <random>
#include <vector>


void Test() {
  std::mt19937_64 random_engine{std::random_device{}()};
  std::vector<int> in{{1, 2, 3, 4, 5}};
  std::size_t m{2};

  std::vector<int> out{};
  std::ranges::sample(in, std::back_inserter(out), m, random_engine);
  assert(out.size() == m);

  for (const int &elem : out) {
    std::cout << elem << std::endl;
  }
}

- ALittleDiff