How to Get a Random Element from a C++ Container

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.

Select N random elements from a List T in C#

Iterate through and for each element make the probability of selection = (number needed)/(number left)

So if you had 40 items, the first would have a 5/40 chance of being selected. If it is, the next has a 4/39 chance, otherwise it has a 5/39 chance. By the time you get to the end you will have your 5 items, and often you'll have all of them before that.

This technique is called selection sampling, a special case of Reservoir Sampling. It's similar in performance to shuffling the input, but of course allows the sample to be generated without modifying the original data.

get random item from listBox c#

var random = new Random();

 int index = random.Next(0, listBox1.Items.Count);
 Console.Writeline(listBox1.Items[index].toString());

Get random element and remove it

You have the solution, and it seems perfectly fine. The idiomatic way to write it in C++ is not to create another class (and please don't inherit from std::vector), but just to write a function:

template <typename T>
void remove_at(std::vector<T>& v, typename std::vector<T>::size_type n)
{
    std::swap(v[n], v.back());
    v.pop_back();
}

Usage:

remove_at(v, 42);

This offers the same exception guarantee as std::swap<T>.

Now if you want to return the object, and you have access to a C++11 compiler, you can do it the following way. The difficult part is to provide the basic exception guarantee in all cases:

template <typename T>
T remove_at(std::vector<T>&v, typename std::vector<T>::size_type n)
{
    T ans = std::move_if_noexcept(v[n]);
    v[n] = std::move_if_noexcept(v.back());
    v.pop_back();
    return ans;
}

Indeed, you don't want the vector to be left in an invalid state if an exception is thrown during a move operation.

associative / random access container

I have been looking for such a data structure for a long time.

Recently, I found quite promising library which has all the functionality that you are looking for.

See the cntree::set with random access in O(log n).

here is the link.
http://dl.dropbox.com/u/8437476/works/countertree/index.html

Although it seems to be under development, I see it is quite usable.

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

Is there a C++ container with reasonable random access that never calls the element type's copy constructor?

I'm pretty sure that the answer here is a rather emphatic "No". By your definition, resize() should allocate new storage and initialize with the default constructor if I am reading this correctly. Then you would manipulate the objects by indexing into the collection and manipulating the reference instead of "inserting" into the collection. Otherwise, you need the copy constructor and assignment operator. All of the containers in the Standard Library have this requirement.

You might want to look into using something like boost::ptr_vector<T>. Since you are inserting pointers, you don't have to worry about copying. This would require that you dynamically allocate all of your objects though.

Fastest way to get a random value from a string array in C#?

Not built in, but easy enough to add...

static readonly Random rand = new Random();
public static T GetRandomValue<T>(T[] values) {
    lock(rand) {
        return values[rand.Next(values.Length)];
    }
}

(the static field helps ensure we don't get repeats if we use it in a tight loop, and the lock keeps it safe from multiple callers)

In C# 3.0, this could be an extension method:

public static T GetRandomValue<T>(this T[] values) {...}

Then you could use it exactly as per your example:

string[] fileLines = File.ReadAllLines(filePath);
string val = fileLines.GetRandomValue();

Get 3 Random elements and 1 preset element from HashSet

You can 'concat' additional list of items to your IEnumerable, but you probably will want to re-shuffle them afterwards:

DifferentAnswers
  .OrderBy(n => Guid.NewGuid())
  .Where(n => n != CorrectAnswer)
  //Needs to be after the Where
  .Take(3)
  // added:
  .Concat(new [] {CorrectAnswer})
  .OrderBy(n => Guid.NewGuid())
  //
  .ToArray();

(of course it assumes you know the CorrectAnswer upfront, just like your example code suggested)

---

Related Topics