Sample without replacement+intersect

Discussion in 'C++' started by Francogrex, May 6, 2008.

  1. Francogrex

    Francogrex Guest

    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

    #include <iostream>
    #include <fstream>
    using namespace std;

    int main(){
    ofstream osdis("dis.txt");
    ofstream oscover("cover.txt");
    srand(10);
    int Ntot=200;
    int Nons=70;
    int i=0,j=0,r=0,t=0;
    int xtot[200];
    int xons[Ntot];
    for (int i = 0; i < Ntot; i++){
    xtot = i;
    }
    for (int i = 0; i < Nons; i++) {
    r = rand()%Ntot + 0;
    t = xtot[r];
    xtot[r] = xtot;
    xons = t;
    }
    int NEPS1cover=150;
    int xEPS1cover[NEPS1cover];
    for (int i = 0; i < NEPS1cover; i++) {
    r = rand()%Ntot + 0;
    t = xtot[r];
    xtot[r] = xtot;
    xEPS1cover = t;
    }
    int R=0,u=0;
    int xEPS1expected[NEPS1cover];
    while(u<Nons){
    int v=0;
    while (v<NEPS1cover){
    cout<<"dis: "<<xons<<"\n";
    cout<<"cover: "<<xEPS1cover[v]<<"\n";
    if (xons==xEPS1cover[v]){
    printf("YES\n");
    R=R+1;
    }
    v=v+1;
    }
    u=u+1;
    }
    for (j=0;j<Nons;j++) osdis<<xons[j]<<"\n";
    for (i=0;i<NEPS1cover;i++) oscover<<xEPS1cover<<"\n";
    cout<<"R :"<<R<<"\n";
    system("PAUSE");
    return 0;
    }
     
    Francogrex, May 6, 2008
    #1
    1. Advertisements

  2. Francogrex

    Christopher Guest



    Add comments, document requirements and algorithm, use meaningful
    variable and function names such that people can decipher your code
    without spending an hour analyzing things like "what the hell is
    NEPS1cover?" and "Whats a Nons?", "is there some reason a variable is
    capitol R while others are lower case u and v? Is he trying to say
    something there?". Glancing over the code as is, I don't have enough
    kindness in my heart to try and figure it out and follow it.
     
    Christopher, May 6, 2008
    #2
    1. Advertisements

  3. Francogrex

    Jerry Coffin Guest

    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::eek:stream_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.
     
    Jerry Coffin, May 7, 2008
    #3
  4. Francogrex

    Lionel B Guest

    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,a[uniform(i,n)]);
    }

    where uniform(i,n) returns a uniform random integer in the range i .. n-1
     
    Lionel B, May 7, 2008
    #4
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.