By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,589 Members | 1,209 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,589 IT Pros & Developers. It's quick & easy.

Select element from Set randomly?

P: n/a
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

Aug 22 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
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
Aug 22 '05 #2

P: n/a
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

Aug 22 '05 #3

P: n/a
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

Aug 22 '05 #4

P: n/a

"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

Aug 22 '05 #5

P: n/a
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
Aug 22 '05 #6

P: n/a
Thank you all for your help!

Best regards,
Robert

Aug 23 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.