Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

c++

iterator

set

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.

like image 249
Frank Avatar asked Jun 16 '10 11:06

Frank


People also ask

Is random access allowed in Set C++?

In fact, if you are thinking of uses of random-access iterators, then you can use random-access iterator in place of any other type of iterator since it is the strongest and the best type of iterator available in the C++ Standard library.

How do you generate a random value from a HashSet?

In order to get random elements from the HashSet object, we need to generate a random number between 0 (inclusive) and the size of the HashSet (exclusive). And then iterate through the set till we reach the element located at the random number position as given below.

How do you generate a random value from a vector in C++?

To generate the random values between 0 and n-1 , we can use the cstdlib's functions rand() and srand() or use any of the standard generators defined in the <random> header introduced in C++11.


2 Answers

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; } 
like image 173
xtofl Avatar answered Sep 22 '22 20:09

xtofl


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.

like image 21
matovitch Avatar answered Sep 23 '22 20:09

matovitch