Generate non-successive combinations.

Question

I have a function that generates combinations of elements in a vector. The number of combinations is usually below 10000, so quite small. I must find a combination that solves a certain problem. If one combination fails, its likely (although not certain) that a similar will fail too. Thus it makes sense to test very different combinations: e.g. [7 1 3] then [9 5 2] etc.

Currently I use code from here (linked in this answer), to generate all combinations. Then I shuffle them and just try them until I found a working combination. Better would be to just create one combination, try it, if it fails, create another one (which is very different)...

Is there a good way to solve this problem?

#include <vector>
#include <algorithm>
#include <iostream>

#include "combinatorics.h"

using namespace std;

int main()
{
    vector<int> v(5);
    iota(begin(v), end(v), 0);

    /* Fill combos with all combinations: choose 3 from v */
    vector<vector<int>> combos;
    auto f = [&] (auto a, auto b)
    {
        combos.emplace_back();
        copy(a, b, back_inserter(combos.back()));
        return false;
    };
    for_each_combination(begin(v), begin(v)+3, end(v), f);

    /* Print all combinations */
    for(auto& combo : combos)
    {
        for(auto i : combo)
            cout<<i<<" ";
        cout<<endl;
    }

    /* Shuffle combos and start trying one combination after the other. */
}

PS. The reason for using this code is, that later on, I most likely will have use for the permutation functions. As of the answer, they seem to perform really well.

In this example I use ints, however, it would be nice to have a solution that works for types which have no >,< operators.