Problem: Generating random indices for a container

[Ross MacGregor]

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

[Adam Fineman]

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

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

- Adam

[Alf P. Steinbach]

On Fri, 22 Aug 2003 21:09:55 GMT, Ross MacGregor <ro***********@shaw.ca> 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.

[Ross MacGregor]

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

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

- Adam

[Adam Fineman]

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

[Ross MacGregor]

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