Re: Sample without replacement+intersect

In article <feeb9a47-303c-46c4-a250-553fd735310b@
8g2000hse.googlegroups.com>, franco@grex.org says...


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:

template <class T, class OutIt>
void rand_select(T const &lower, T const &upper, size_t N, OutIt &it) {
    std::set<T> selection;

    for (size_t i=0; i<N; ++i)
        selection.insert(rand_lim(lower, upper);
    while (selection.size() < N)
        selection.insert(rand_lim(lower, upper);
}

Where rand_lim is defined something like this:

int rand_lim(int limit) {
/* return a random number between 0 and limit inclusive.
 */

    int divisor = RAND_MAX/(limit+1);
    int retval;

    do {
        retval = rand() / divisor;
    } while (retval > limit);

    return retval;
}

int rand_lim(int lower, int upper) {
    int range = abs(upper-lower);

    return rand_lim(range) + lower;
}

You might prefer to use the uniform_int from TR1, which (I believe) has
the same general intent as this, though it has a substantially different
interface.

--
    Later,
    Jerry.

The universe is a figment of its own imagination.