Velocity Reviews > C++ > Problem: Generating random indices for a container

# Problem: Generating random indices for a container

Ross MacGregor
Guest
Posts: n/a

 08-22-2003

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

Guest
Posts: n/a

 08-22-2003
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.
>

--------------
#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[i] << ' ';
cout << '\n';

return 0;
}
----------------

Alf P. Steinbach
Guest
Posts: n/a

 08-22-2003
On Fri, 22 Aug 2003 21:09:55 GMT, Ross MacGregor <(E-Mail Removed)> 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
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.

Ross MacGregor
Guest
Posts: n/a

 08-22-2003

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 wrote:
>
>>
>> I have a very simple yet complicated problem. I want to generate a
>> random list of indices (int's) for a container.
>>

>
> --------------
> #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[i] << ' ';
> cout << '\n';
>
> return 0;
> }
> ----------------
>
>

Guest
Posts: n/a

 08-24-2003
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).

Ross MacGregor
Guest
Posts: n/a

 08-25-2003

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

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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post VK Javascript 15 05-02-2010 03:43 PM globalrev Python 4 04-20-2008 08:12 AM Steven T. Hatton C++ 4 12-05-2004 07:10 AM Maitre Bart C++ 2 02-11-2004 12:11 AM Vivi Orunitia C++ 11 02-04-2004 08:09 AM