Re: Sample without replacement+intersect
On Tue, 06 May 2008 23:25:36 -0600, Jerry Coffin wrote:
In article <feeb9a47-303c-46c4-a250-553fd735310b@
8g2000hse.googlegroups.com>, franco@grex.org says...
Hi, I'm trying to sample without replacement some numbers (xons:70
values out of 1 to 200 and xEPS1cover:150 values out of 1 to 200). Then
I'm trying to intersect both samples to see how many are in common. I
have tried to write the code below, but I cannot seem to sample without
replacement (there are recurrent numbers within the same sample, I
don't want that) and I cannot either find the exact intersection
between the two samples. Can anyone please help or give some hints.
Thanks
I'm afraid I'm a bit too lazy to figure out your code (Google appears to
have lost the indentation).
One easy (if less than perfectly efficient) way to get samples without
replacements is to generate the numbers in the range you want
(consecutively), then select the first N items after scrambling them
into a random order:
template <class T, class OutIt>
void rand_select(T const &lower, T const &upper, size_t N, OutIt &it) {
std::vector<T> temp;
for (T i=lower; i!=upper; ++i)
temp.push_back(i);
std::random_shuffle(temp.begin(), temp.end()); std::copy
(temp.begin(),
temp.begin()+N, it);
}
Used something like:
std::vector<int> items;
rand_select(1, 200, 70, std::back_inserter(items));
std::copy(items.begin(), items.end(),
std::ostream_iterator<int>(std::cout, "\t"));
For the numbers you've given above, this method is probably perfectly
adequate. If the numbers might vary, especially so you're selecting only
a tiny part of a huge range, this can be quite inefficient, and other
ways will work better. In the latter case (if you're SURE the number
being selected is small compared to the range, you're better off with
something like selecting random numbers in the range, and inserting them
into a set until you get as many numbers as you want:
I use a "partial shuffle" like:
// Select k random elements without replacement from array a
// (of length n) and put in first k elements of a
template<typename T> void partial_shuffle(T* const a, const size_t n, const size_t k)
{
for (size_t i=0;i<k;++i) std::swap(a[i],a[uniform(i,n)]);
}
where uniform(i,n) returns a uniform random integer in the range i .. n-1
--
Lionel B