Combination of a Collection with Repetitions

Question

There are a lot of links on http://stackoverflow.com for how to do combinations: Generating combinations in c++ But these links presume to draw from an infinite set without repetition. When given a finite collection which does have repetition, these algorithms construct duplicates. For example you can see the accepted solution to the linked question failing on a test case I constructed here: http://ideone.com/M7CyFc

Given the input set: vector<int> row {40, 40, 40, 50, 50, 60, 100};

I expect to see:

• 40 40 40
• 40 40 50
• 40 40 60
• 40 40 100
• 40 50 50
• 40 50 60
• 40 50 100
• 40 60 100
• 50 50 60
• 50 50 100
• 50 60 100

Obviously I can use the old method store the output and check for duplicates as I generate, but this requires a lot of extra memory and processing power. Is there an alternative that C++ provides me?

Answer 1

You can do something like this (maybe avoiding the recursion):

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

using std::cout;
using std::vector;

void perm( const vector<int> &v, vector<vector<int>> &p, vector<int> &t, int k, int d) {
    for ( int i = k; i < v.size(); ++i ) {
        // skip the repeted value
        if ( i != k && v[i] == v[i-1]) continue;
        t.push_back(v[i]);
        if ( d > 0 ) perm(v,p,t,i+1,d-1);
        else p.push_back(t);
        t.pop_back();
    }
}

int main() {
    int r = 3;
    vector<int> row {40, 40, 40, 50, 50, 60, 100};
    vector<vector<int>> pp;
    vector<int> pe;

    std::sort(row.begin(),row.end()); // that's necessary
    perm(row,pp,pe,0,r-1);

    cout << pp.size() << '\n';
    for ( auto & v : pp ) {
        for ( int i : v ) {
            cout << ' ' << i;
        }
        cout << '\n';
    }
    return 0;
}

Which outputs:

11
 40 40 40
 40 40 50
 40 40 60
 40 40 100
 40 50 50
 40 50 60
 40 50 100
 40 60 100
 50 50 60
 50 50 100
 50 60 100

I know, it's far from efficient, but if you get the idea you may come out with a better implementation.