On Tue, 06 May 2008 23:25:36 -0600, Jerry Coffin wrote:
> In article <feeb9a47-303c-46c4-a250-553fd735310b@[EMAIL PROTECTED]
> 8g2000hse.googlegroups.com>, franco@[EMAIL PROTECTED]
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
|
