Select element from Set randomly?

Discussion in 'C++' started by Robert, Aug 22, 2005.

  1. Robert

    Robert Guest

    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
     
    Robert, Aug 22, 2005
    #1
    1. Advertisements

  2. What's "Set"? Do you mean 'std::set' or some other implementation?
    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
     
    Victor Bazarov, Aug 22, 2005
    #2
    1. Advertisements

  3. Robert

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Aug 22, 2005
    #3
  4. Robert

    Marc Mutz Guest

    Robert wrote:
    <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, Aug 22, 2005
    #4
  5. Robert

    Marc Mutz Guest

    + random_sample_n, so you can write
    Marc,
    love-hates CTRL-K
     
    Marc Mutz, Aug 22, 2005
    #5
  6. Robert

    Mike Wahler Guest

    #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
     
    Mike Wahler, Aug 22, 2005
    #6
  7. Robert

    Robert Guest

    Thank you all for your help!

    Best regards,
    Robert
     
    Robert, Aug 23, 2005
    #7
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.