Select element from Set randomly?

[Robert]

Hi all,

I have a Set contain several elements.

I want to do:
(1) Select one element from Set randomly;
(2) Delete this element from Set;
(3) If Set!=empty, goto(1);else, end.

Is there any easy approach?

Best regards,
Robert

 

[Victor Bazarov]

I have a Set contain several elements.

What's "Set"? Do you mean 'std::set' or some other implementation?

I want to do:
(1) Select one element from Set randomly;
(2) Delete this element from Set;
(3) If Set!=empty, goto(1);else, end.

Is there any easy approach?

What do you mean by "easy approach"? If I presume 'std::set', then
you can get the number of elements in the set ('size' member), call
'rand' (to get the random number), scale it to the size, get the
set beginning iterator, advance it (using 'std::advance'), then
erase the element pointed to by that iterator. Repeat until empty.
How much easier than that do you need?

BTW, what's the importance of the element erased to be random?

V

 

[Kai-Uwe Bux]

Hi all,

I have a Set contain several elements.

I want to do:
(1) Select one element from Set randomly;
(2) Delete this element from Set;
(3) If Set!=empty, goto(1);else, end.

Is there any easy approach?

Yes: clear the set.
[this instruction has the same pre- and postconditions as your pseudo code]


But, I presume you really want something different, namely you want to keep
track of the order in which the elements are drawn. Here is how you can
achieve an equivalent effect:

Let s be your std::set<T> object.

std::vector<T> deletion_order ( s.begin(), s.end() );
s.clear();
std::random_shuffle( deletion_order.begin(), deletion_order.end() );

Now just pretend that the objects have been deleted in the order represented
by deletion_order.



Best

Kai-Uwe Bux

 

[Marc Mutz]

Robert wrote:

I have a Set contain several elements.

I want to do:
(1) Select one element from Set randomly;
(2) Delete this element from Set;
(3) If Set!=empty, goto(1);else, end.

Is there any easy approach?

<snip>

If you have the SGI's STL extensions, there's
void random_visit( const std::set<Element> & set,
const Visitor & visitor )
{
std::vector<Element> v;
v.reserve( set.size() );
random_sample_n( set.begin(), set.end(),
std::back_inserter( v ), set.size() );
for_each( v.begin(), v.end(), visitor );
}

Otherwise, you can use copy+random_shuffle:
std::copy( set.begin(), set.end(),
std::back_inserter( v ) );
std::random_shuffle( v.begin(), v.end() );

Marc

 

[Marc Mutz]

If you have the SGI's STL extensions, there's

+ random_sample_n, so you can write

void random_visit( const std::set<Element> & set,
const Visitor & visitor )
{
std::vector<Element> v;
v.reserve( set.size() );
random_sample_n( set.begin(), set.end(),
std::back_inserter( v ), set.size() );
for_each( v.begin(), v.end(), visitor );
}

Marc,
love-hates CTRL-K

 

[Mike Wahler]

Hi all,

I have a Set contain several elements.

I want to do:
(1) Select one element from Set randomly;
(2) Delete this element from Set;
(3) If Set!=empty, goto(1);else, end.

Is there any easy approach?

#include <iostream>
#include <iterator>
#include <set>
#include <stdlib.h>
#include <string>
#include <time.h>

void show(const std::set<int>& s, const std::string prefix)
{
std::set<int>::const_iterator it(s.begin());
std::set<int>::const_iterator en(s.end());

std::cout << prefix;

while(it != en)
std::cout << *it++ << '\n';

std::cout.put('\n');
}

int rand_range(int lo, int hi)
{
return lo +
(int)((double)rand() /
((double)RAND_MAX + 1) * (hi - lo + 1));
}

int main()
{
srand((unsigned int)time(0));
std::set<int> s;

for(std::set<int>::size_type i = 0; i < 10; ++i)
s.insert(i);

show(s, "Initial values:\n");

while(!s.empty())
{
std::set<int>::iterator it(s.begin());
std::advance(it, rand_range(0, s.size() - 1));
int i = *it;
s.erase(it);
std::cout << i << " deleted\n\n";
show(s, "Current values:\n");
}

return EXIT_SUCCESS;
}

Of course the end result could be achieved much more
succintly:

s.clear();

-Mike

 

[Robert]

Thank you all for your help!

Best regards,
Robert