集合与重复的结合 [英] Combination of a Collection with Repetitions

问题描述

http://stackoverflow.com 上有很多链接，可用于进行组合: http://ideone.com/M7CyFc

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

给出输入集: vector< int>第{40，40，40，50，50，60，100};

我希望看到:

• 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

显然，我可以使用旧方法存储输出并在生成时检查重复项，但这需要大量额外的内存和处理能力.C ++是否可以替代我?

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?

推荐答案

您可以执行以下操作(也许可以避免递归):

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;
}

哪个输出:

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.

这篇关于集合与重复的结合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！