How to select a random element in std::set?

Question

How can I select a random element in an std::set?

I naively tried this:

int GetSample(const std::set<int>& s) {
  double r = rand() % s.size();
  return *(s.begin() + r); // compile error
}

But the operator+ is not allowed in this way.

Solution 1

You could use the std::advance method.

#include <set>
#include <algorithm>

int main() {
  using namespace std;
  // generate a set...
  set<int> s;
  for( int i = 0; i != 10; ++i ) s.insert(i);
  auto r = rand() % s.size(); // not _really_ random
  auto n = *select_random(s, r);
}

Where

template<typename S>
auto select_random(const S &s, size_t n) {
  auto it = std::begin(s);
  // 'advance' the iterator n times
  std::advance(it,n);
  return it;
}

Solution 2

First Solution : O(log n) in time / O(1) in space (not uniform !)

A hypothesized in a comment above, it can be done in O(log(n)) (vs O(n) for std::advance) without a vector (using O(n) more space) by using the method I describe here.

Essentially, you :

• check if the set is empty (if it is, there is no hope)
• generate a random value
• if already there return it else insert it
• get one iterator it on it
• get the random element as *(it++) or *(set.begin()) if it at the end
• return it not before deleting the element you inserted

n.b : As pointed out by Aaron the element is not chosen uniformly at random. You need to build the random element with the same distribution than the elements in the set to approach a uniform polling.

Second Solution : O(1) in time / O(n) in space (uniform)

davidhigh already gave the solution with a vector but there is a problem because when you pop an element of your stack, you will have to perform a linear search in O(n) or you can rebuild your vector each time you want to retrieve a random element but that is O(n) too.

To avoid this problem and keep the insert/delete to O(log n), you can keep an std::unordered_set and use a similar method to the first solution to get a random element in O(1).

p.s : If your elements are large you can use an unordered set of pointers (with a modified hasher) to spare some memory.

Solution 3

C++17 std::sample

This will be a convenient, although not very efficient (O(n)) method:

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

int main() {
    std::set<int> in{1, 2, 3, 5, 7};
    std::vector<int> out;
    std::sample(in.begin(), in.end(), std::back_inserter(out),
                3, std::mt19937{std::random_device{}()});
    for (auto i : out)
        std::cout << i << std::endl;
}

But I think that for efficiency you just need to copy to another type of structure: How to select a random element in std::set in less than O(n) time?

Solution 4

If the random access is important and you can live with O(N) average effort for the insertion, then the workaround given in this paper might be convenient.

The main idea there is to use a sorted vector, and then for lookup the function std::lower_bound. This, the lookup takes O(log N) just as in a normal set. Further, (random) insertion takes O(N), as all following elements must be shifted just like in a normal vector (and possibly a reallocation is performed). Insertion at the back, however, is constant (except for the reallocation. You can avoid this by calling reserve() with a large enough storage).

Finally, the main point of the question: Random access is O(1). Just draw a random number i from a uniform distribution in [0, V.size()-1], and return the corresponding element V[i].

Here is the code basis out of the paper, which implements this sorted vector. Extend it as needed:

template <class T, class Compare = std::less<T> >
struct sorted_vector {
 using std::vector;
 using std::lower_bound;
 vector<T> V;
 Compare cmp; 
 typedef typename vector<T>::iterator iterator;
 typedef typename vector<T>::const_iterator const_iterator;
 iterator begin() { return V.begin(); }
 iterator end() { return V.end(); }
 const_iterator begin() const { return V.begin(); }
 const_iterator end() const { return V.end(); }

 //...if needed, implement more by yourself

 sorted_vector(const Compare& c = Compare()) : V(), cmp(c) {}
 template <class InputIterator>
 sorted_vector(InputIterator first, InputIterator last, Const Compare& c = Compare())
 : V(first, last), cmp(c)
 {
 std::sort(begin(), end(), cmp);
 }

 //...

 iterator insert(const T& t) {
     iterator i = lower_bound(begin(), end(), t, cmp);
     if (i == end() || cmp(t, *i))
        V.insert(i, t);
      return i;
 }
 const_iterator find(const T& t) const {
     const_iterator i = lower_bound(begin(), end(), t, cmp);
      return i == end() || cmp(t, *i) ? end() : i;
 }
};

For a more sophisticated implementation, you might also consider this page.

EDIT: or even better, use boost::container::flat_set, which implements the set using the idea above, i.e. as a sorted vector.

Solution 5

int GetSample(const std::set<int>& s) {
  double r = rand() % s.size();
  std::set<int>::iterator it = s.begin();
  for (; r != 0; r--) it++;
  return *it;
}

would be one way of doing it, although not pretty;

View more solutions

Comments

[Frank]

Oh, I forgot about that method. Thanks, that's exactly what I need.

[MSalters]

Any solution will be O(N). Proof is left as an exercise, hint: how many elements of a std::set can be reached in constant time?

[Kiscsirke]

Could be O(logN). std::set is stored in some kind of tree, there could potentially be a solution that just goes down on one of the branches, and is done.

[Aaron McDaid]

That is random yes, but it is not uniformly at random from the current elements of the set. And we can assume the questioner wants uniformity. Although maybe this is not entirely necessary

[matovitch]

Indeed though if you generate your element with a distribution that look like the set that would approach it. We don't have this issue with the unordered_set (see the link in the answer). Need to think about it...

[Gennady Proskurin]

This code is incorrect, you cannot simply check double for equality. And why double here?

[Jason C]

If you know the set is not going to change after you start taking random samples, or it changes very infrequently, you could also cache it in a vector when it changes and just pick from there. You could wrap that cached set up any way you please to make it transparent (writes invalidate cache, cache rebuilt if invalid on read).

[davidhigh]

The method in my answer using a sorted vector is O(1).

[Jonas Greitemann]

@davidhigh True, but in that case insertion and removal are O(N). That seems like cheating, but it depends on the use-case, of course. When you fill the vector once, that's fine.

[davidhigh]

@Jonas: sure, but the question here was only about random selection ... so I didn't care about the others :-)

[Jonas Greitemann]

@Kiscsirke You're right that with balanced search trees you can have O(log(N)) for insertion, removal, and random access. However, the latter requires that nodes store how many children they have to either their left or right. This needs to be updated during insertion, removal, and rebalancing. Since std::set and std::map hide the tree-internals from the user, they cannot be used to achieve this. I ended up implementing my own search tree. It's definitely possible to get O(log(N)) lookup.

[Sasha Kondrashov]

this answer would be much better if it answered the question "how can I select a random element from a set", currently as far as I can tell it shows neither randomness nor element selection, though it gives you the tools to piece it together

[xtofl]

@Timofey that's right. The 'problem' OP had was not the question he asked :). Updated my answer accordingly.

[Sasha Kondrashov]

@xtofl it was a good answer, but it's that much better if the whole solution is given! really appreciate it, thank you