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. Advertising

  2. Ross MacGregor

    Adam Fineman Guest

    Ross MacGregor wrote:
    >
    > I have a very simple yet complicated problem. I want to generate a
    > random list of indices (int's) for a container.
    >

    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
     
    Adam Fineman, Aug 22, 2003
    #2
    1. Advertising

  3. On Fri, 22 Aug 2003 21:09:55 GMT, Ross MacGregor <> wrote:

    >
    >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].


    That last is a more succinct statement of the requirements.




    >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.



    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.



    >void RandomIndices(
    > int in_count,
    > int in_range,
    > IntVector & out_index_list)


    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.



    >{
    > 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);
    > }
    > }
    >}


    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);
    }
    }

    Adam Fineman wrote:
    > Ross MacGregor wrote:
    >
    >>
    >> I have a very simple yet complicated problem. I want to generate a
    >> random list of indices (int's) for a container.
    >>

    > 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
    >
     
    Ross MacGregor, Aug 22, 2003
    #4
  5. Ross MacGregor

    Adam Fineman Guest

    Ross MacGregor wrote:
    >
    > Yes, swapping would work much better, thank you!
    >
    > Here what I have now, I am essentially implementing a partial random
    > shuffle:
    > <snip>


    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. Adam Fineman wrote:
    > 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


    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. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. sugaray

    problem with generating random numbers !

    sugaray, Sep 13, 2003, in forum: C Programming
    Replies:
    2
    Views:
    401
    Tom Zych
    Sep 14, 2003
  2. Xavier Barthelemy

    problem in reading indices

    Xavier Barthelemy, Dec 13, 2007, in forum: Python
    Replies:
    2
    Views:
    250
    Bjoern Schliessmann
    Dec 13, 2007
  3. globalrev
    Replies:
    4
    Views:
    811
    Gabriel Genellina
    Apr 20, 2008
  4. Jean-Michel Pichavant
    Replies:
    2
    Views:
    542
    Arnaud Delobelle
    Feb 15, 2010
  5. VK
    Replies:
    15
    Views:
    1,322
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page