Problem: Generating random indices for a container

Discussion in 'C++' started by Ross MacGregor, Aug 22, 2003.

  1. I have a very simple yet complicated problem. I want to generate a
    random list of indices (int's) for a container.

    Let's say I have a container with 10 items and I want a list of 3 random
    indices for that container.

    So I need to generate 3 unique numbers from integer range [0-9].

    There seems to be no simple and efficient way to do this. Any
    implementation I have come up with involves maintaining a list of
    indices that requires random access and deletions.

    Here is my implementation below, does anyone know of an alternate method
    of solving this problem?

    void RandomIndices(
    int in_count,
    int in_range,
    IntVector & out_index_list)
    {
    assert( in_count <= in_range );

    if( in_count > in_range / 2 )
    {
    // We are selecting a majority of indices.
    // Simply remove the undesirable indices from the list.

    int remove_count = in_range - in_count;

    // Generate a list of numbers from 0 to (n_range - 1)
    out_index_list.resize(in_range);
    std::generate(
    out_index_list.begin(),
    out_index_list.end(),
    SequenceGenerator());

    for(int i=0; i<remove_count; ++i)
    {
    int n( RandomNumber(out_index_list.size()) );
    out_index_list.erase(out_index_list.begin() + n);
    }
    }
    else
    {
    // We are selecting a minority of indices
    // Create a temporary list with entire range of indices
    // and select our list from it

    // Temporary list of indices
    IntVector list(in_range);

    // Generate a list of numbers from 0 to (n_range - 1)
    std::generate(
    list.begin(),
    list.end(),
    SequenceGenerator());

    out_index_list.reserve(in_count);

    for(int i=0; i<in_count; ++i)
    {
    int n( RandomNumber(list.size()) );
    IntVector::iterator p( list.begin() + n );

    out_index_list.push_back(*p);
    list.erase(p);
    }
    }
    }
     
    Ross MacGregor, Aug 22, 2003
    #1
    1. Advertisements

  2. Ross MacGregor

    Adam Fineman Guest

    How about this?

    --------------
    #include <vector>
    #include <algorithm>
    #include <iostream>
    #include <iterator>

    using namespace std;

    int
    main()
    {
    vector<int> v;
    // fill the vector with whatever
    copy(istream_iterator<int>(cin), istream_iterator<int>(),
    back_inserter(v));

    typedef vector<int>::const_iterator Iter;
    vector<Iter> it;
    for (Iter i = v.begin(); i != v.end(); ++i)
    it.push_back(i);

    // output three random values from v
    random_shuffle(it.begin(), it.end());
    for (vector<Iter>::size_type i = 0; i < 3; ++i)
    cout << *it << ' ';
    cout << '\n';

    return 0;
    }
     
    Adam Fineman, Aug 22, 2003
    #2
    1. Advertisements

  3. That last is a more succinct statement of the requirements.




    A) Shuffle a list of the numbers 0 through 9, then pick any three.
    B) Maintain a bitset of already used numbers.
    C) When the range is sufficiently large, a pseudo-random sequence
    with period equal to or slightly larger than the range.


    I suggest using just comments for "in" and "out". Prefixes
    clutter the text, lowering readability. And low readability
    introduces just the possible confusion you're trying to avoid.

    Also, personally I'd use 'unsigned' or even 'size_t', to most
    accurately reflect the expected range.

    But regarding that the community is split 50/50, with some people
    having _very_ strong feelings about what everybody else should do.


    It seems like a lot of duplicated code.
     
    Alf P. Steinbach, Aug 22, 2003
    #3
  4. Yes, swapping would work much better, thank you!

    Here what I have now, I am essentially implementing a partial random
    shuffle:

    [I guess if I wanted to get crazy I could create a custom int type that
    would construct itself into a sequence during resize operation...hmmm]

    void RandomIndices(
    int in_count,
    int in_range,
    IntVector & out_index_list)
    {
    assert( in_count <= in_range );

    out_index_list.resize(in_range);

    IntVector::iterator p = out_index_list.begin();
    IntVector::iterator end = out_index_list.end();

    std::generate(p, end, SequenceGenerator());

    --in_range;
    if( in_range )
    {
    for(int i=0; i<in_count; ++i)
    {
    int n( RandomNumber(in_range) );

    std::swap(*p,*(p + n));

    --in_range;
    ++p;
    }

    out_index_list.resize(in_count);
    }
    }

     
    Ross MacGregor, Aug 22, 2003
    #4
  5. Ross MacGregor

    Adam Fineman Guest

    Why are you reimplementing random_shuffle()? It's part of the standard
    library, and it's complexity is guaranteed to be linear in (last - first).

    - Adam
     
    Adam Fineman, Aug 24, 2003
    #5
  6. It is an optimization. I am implementing a partial_random_shuffle() that
    does not exist in STL yet. It is the inverse function of partial_sort().
     
    Ross MacGregor, Aug 25, 2003
    #6
    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.