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]

Robert wrote:

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]

Robert wrote:

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:
<snip>

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

[Mike Wahler]

"Robert" <zh*******@gmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...

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

Best regards,
Robert

[Marc Mutz]

Marc Mutz wrote:

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

[Robert]

Thank you all for your help!

Best regards,
Robert