Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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

 
Reply With Quote
 
 
 
 
Adam Fineman
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.
>

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

 
Reply With Quote
 
 
 
 
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
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.



 
Reply With Quote
 
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);
}
}

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
>


 
Reply With Quote
 
Adam Fineman
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).

- Adam

 
Reply With Quote
 
Ross MacGregor
Guest
Posts: n/a
 
      08-25-2003

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

 
Reply With Quote
 
 
 
Reply

Thread Tools

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Math.random() and Math.round(Math.random()) and Math.floor(Math.random()*2) VK Javascript 15 05-02-2010 03:43 PM
random.random(), random not defined!? globalrev Python 4 04-20-2008 08:12 AM
std::transform container => std::abs(container) Steven T. Hatton C++ 4 12-05-2004 07:10 AM
STL: container's values setup by another container Maitre Bart C++ 2 02-11-2004 12:11 AM
std::container::iterator vs std::container::pointer Vivi Orunitia C++ 11 02-04-2004 08:09 AM



Advertisments