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(),
SequenceGenerat or());
for(int i=0; i<remove_count ; ++i)
{
int n( RandomNumber(ou t_index_list.si ze()) );
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(),
SequenceGenerat or());
out_index_list. reserve(in_coun t);
for(int i=0; i<in_count; ++i)
{
int n( RandomNumber(li st.size()) );
IntVector::iter ator p( list.begin() + n );
out_index_list. push_back(*p);
list.erase(p);
}
}
}
Comment