472,779 Members | 1,827 Online

# Problem: Generating random indices for a container

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

Jul 19 '05 #1
5 2821
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;
}
----------------

Jul 19 '05 #2
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
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.

Jul 19 '05 #3

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

Jul 19 '05 #4
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).

Jul 19 '05 #5

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

Jul 19 '05 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 18 by: Mark | last post by: Hi Yall I have a page where I want 5 images to appear, randomly selected from a pool of 50 images called 1.jpg to 50.jpg The following code works nicely, except for one (probably obvious)... 21 by: Andreas Lobinger | last post by: Aloha, i wanted to ask another problem, but as i started to build an example... How to generate (memory and time)-efficient a string containing random characters? I have never worked with... 6 by: moi | last post by: hi, i have an assignment to put 6 pseudo random numbers into an array to simulate drawing 6 lottery numbers between 1-49. the code i have to do this so far is listed below. i dont think its far... 41 by: AngleWyrm | last post by: I have created a new container class, called the hat. It provides random selection of user objects, both with and without replacement, with non-uniform probabilities. Uniform probabilities are a... 1 by: steflhermitte | last post by: Dear cpp-ians, I want to apply a stratified sampling on an image. Following simplified example will explain my problem. The original image I with nrows and ncols is now a vector V of length... 8 by: laniik | last post by: Hi. I have a problem using STL's built in sort that seems impossible to get around. if i have: -------------------------------- struct object { int val; } 15 by: Hemant Shah | last post by: Folks, We have an SQL statement that was coded in an application many years ago (starting with DB V2 I think). When I upgraded to UDB 8.2, the optimizer does not use optimal path to access the... 0 by: toton | last post by: Hi, I have a complex design of some dynamic situation. First I am posting the design, then a few questions regarding the problem I am facing. Hope some of the experts will answer the questions.... 36 by: Krustov | last post by: What is wrong with this php code ? . (it works fine - but something that just works isnt good enough for this newsgroup is it)