# Problem: Generating random indices for a container

Discussion in 'C++' started by Ross MacGregor, Aug 22, 2003.

1. ### Ross MacGregorGuest

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

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

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

3. ### Alf P. SteinbachGuest

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
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
4. ### Ross MacGregorGuest

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

Ross MacGregor, Aug 22, 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).

6. ### Ross MacGregorGuest

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