set_difference not always returns the right answer

Question

I am currently working on an evolutionary algorithm. I write a program to implement the crossover function, i.e., exchange k elements between vectors A and B. Here is the code:

#include <algorithm>
#include <cstdio>
#include <ctime>
#include <iostream>
#include <iterator>
#include <random>
#include <set>
#include <vector>

using namespace std;

vector<int> reservoir_sampling(vector<int> input, int k)
{
    vector<int> output(k);
    int i;
    for (i = 0; i < k; i++)
    {
        output[i] = input[i];
    }
    srand(time(nullptr));
    while(i < input.size())
    {
        int j = rand() % (i+1);
        if (j < k)
        {
            output[j] = input[i];
        }
        i++;
    }
    return output;
}

template<typename T>
void vprintf(vector<T> V)
{
    for (T v : V)
    {
        cout << v << " ";
    }
    cout << endl;
}

void test()
{
    // crossover between A and B at k points
    vector<int> A = {0, 1, 2, 3, 4, 5};
    vector<int> B = {6, 7, 8, 9};
    printf("A: ");
    vprintf(A);
    printf("B: ");
    vprintf(B);
    int k = 2;
    vector<int> outers = reservoir_sampling(A, k);
    vector<int> inners = reservoir_sampling(B, k);
    printf("outers: ");
    vprintf(outers);
    printf("inners: ");
    vprintf(inners);
    // uS = A + inners
    vector<int> uS;
    set_union(A.begin(), A.end(), inners.begin(), inners.end(), inserter(uS, uS.end()));
    sort(uS.begin(), uS.end());
    printf("uS =  A + inners: ");
    vprintf(uS);
    // dS = uS - outers
    vector<int> dS;
    set_difference(uS.begin(), uS.end(), outers.begin(), outers.end(), inserter(dS, dS.end()));
    sort(dS.begin(), dS.end());
    printf("dS = uS - outers: ");
    vprintf(dS);
}

int main()
{
    test();
    return 0;
}

Sometimes, the output is right, like:

A: 0 1 2 3 4 5
B: 6 7 8 9
outers: 3 4
inners: 9 7
uS =  A + inners: 0 1 2 3 4 5 7 9
dS = uS - outers: 0 1 2 5 7 9

Sometimes, the output is not right, like:

A: 0 1 2 3 4 5
B: 6 7 8 9
outers: 3 1
inners: 9 7
uS =  A + inners: 0 1 2 3 4 5 7 9
dS = uS - outers: 0 1 2 4 5 7 9

It turns out set_union is always OK, but set_difference is not. I don't have any clue where I am wrong. Almighty users of SO, please help me out!

The copying loop in `reservoir_sampling` isn't needed, you can do it at initialization: `std::vector output(begin(input), begin(input) + k);` Assuming that `k` is smaller or equal to `input.size()` of course. — Some programmer dude, Dec 11 '19 at 11:46
And please [don't do `using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Considering that you `#include ` and define a function `vprintf` (which because of the `using` directive overloads [`std::vprintf`](https://en.cppreference.com/w/cpp/io/c/vfprintf)) that could lead to some confusion. — Some programmer dude, Dec 11 '19 at 11:48
Please use "+" only for sum; it's confusing and ambiguous here. — curiousguy, Dec 11 '19 at 12:47

score 2 · Answer 1 · edited Jun 20 '20 at 09:12

You violate the preconditions of std::set_union and std::set_difference:

Constructs a sorted union beginning at d_first consisting of the set of elements present in one or both sorted ranges [first1, last1) and [first2, last2).

Copies the elements from the sorted range [first1, last1) which are not found in the sorted range [first2, last2) to the range beginning at d_first.

The reservoir_sampling function does not produce a sorted vector in the general case. The behaviour of your program is undefined.

The standard library provides std::sample function for random sampling. It preserves the relative order of selected elements if you give it a pair of forward or random access iterators.

template<typename T>
std::vector<T> sampling(const std::vector<T>& input, std::size_t k) {
    std::vector<T> output;
    output.reserve(k);
    std::sample(input.begin(), input.end(), std::back_inserter(output),
        k, std::mt19937{std::random_device{}()});    

    // the relative order of elements in output is the same as in input
    return output;
}

Exactly! I sort both inners and outers, and then the result turns right! Thank you! — cmjdxy, Dec 11 '19 at 12:44

set_difference not always returns the right answer

1 Answers1