How to Select a Random Element in Std::Set

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

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;
}

How to efficiently select a random element from a std::set

Use boost::container::flat_set instead:

boost::container::flat_set<int> set;
// ...
auto it = set.begin() + rand() % set.size();

Insertions and deletions become O(N) though, I don't know if that's a problem. You still have O(log N) lookups, and the fact that the container is contiguous gives an overall improvement that often outweighs the loss of O(log N) insertions and deletions.

add random element of a set to a list and remove it from original set

I'm not sure why you are using std::set... probably because it sorts the cards automatically. I would use std::vector and sort manually (std::sort).

I have to fill in some blanks on what you are trying to do in the code, as you didn't post a working, complete example.

I would suggest using encapsulation and moving the drawn cards instead of copying before deletion. E.g.

#include <random>
#include <string>
#include <set>
#include <vector>
#include <numeric>

class Random {
private:
    std::default_random_engine generator{};
public:
    int operator()(int maxValue) { return generator() % maxValue; }
};

class Card {
private:
    std::string name{};
public:
    Card() : name{} {}
    Card& operator= (int i) {
        name = std::to_string(i);
        return *this;
    }
    friend bool operator<(Card const& lhs, Card const& rhs) {
        return lhs.name < rhs.name; // or some other sorting.
    }
};

class Player {
private: 
    std::set<Card> cards{};
public:
    void AddCard(Card&& card) noexcept {
        cards.emplace(std::move(card));
    }
};

int main() {
    //fill the deck
    std::vector<Card> deck(42); // instead of remaining cards... why would this be a set?
    std::iota(std::begin(deck), std::end(deck), 1); // fill 1 to 42

    Random random{};

    std::vector<Player> players(4);
    while (deck.size() > 0) { // distribute the whole deck.
        for (auto& player : players) {
            if (deck.empty()) break; // if cards in desck is not equaly dividable between players
            auto randIdx = random(deck.size());
            player.AddCard(std::move(deck[randIdx]));  // move one card
            deck.erase(std::next(std::begin(deck), randIdx));  // and remove it from deck
        }
    }
}

Picking a random element from a set

int size = myHashSet.size();
int item = new Random().nextInt(size); // In real life, the Random object should be rather more shared than this
int i = 0;
for(Object obj : myhashSet)
{
    if (i == item)
        return obj;
    i++;
}

Random element from unordered_set in O(1)

I believe you have misinterpreted the meaning of "random access", as it was used in those cases you're referring to.

"Random access" doesn't have anything to do with randomness. It means to access an element "at random", i.e. access any element anywhere in the container. Accessing an element directly, such as with std::vector::operator[] is random access, but iterating over a container is not.

Compare this to RAM, which is short for "Random Access Memory".

How to get a random element from a C++ container?

C++17 std::sample

This is a convenient method to get several random elements without repetition.

main.cpp

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

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

Compile and run:

g++-7 -o main -std=c++17 -Wall -Wextra -pedantic main.cpp
./main

Output: 3 random numbers are picked from 1, 2, 3, 5, 7 without repetition.

For efficiency, only O(n) is guaranteed since ForwardIterator is the used API, but I think stdlib implementations will specialize to O(1) where possible (e.g. vector).

Tested in GCC 7.2, Ubuntu 17.10. How to obtain GCC 7 in 16.04.

C++ random number from a set

Say these numbers are in a set of size 5, all you gotta do is find a random value multiplied by 5 (to make it equi probable). Assume the rand() method returns you a random value between range 0 to 1. Multiply the same by 5 and cast it to integer you will get equiprobable values between 0 and 4. Use that to fetch from the index.

I dont know the syntax in C++. But this is how it should look

my_rand_val = my_set[(int)(rand()*arr_size)]

Here I assume rand() is a method that returns a value between 0 and 1.

---

Related Topics