c++ - 在 C++ 中获取所有排列的最有效方法

Question

我正在尝试用 C++ 计算很多组合。我自己想出了下面的实现，但是效率并不理想。得到 C-18-2(每 2 个 18 的组合)需要 3 多秒，我相信这可以在更短的时间内完成。

 vector<vector<int>> Mytool::combo2(int len){
    MatrixXd ma = MatrixXd::Zero(len*len*len,2);
    int ind = 0;
    for (int i = 0 ;i<len;i++){
        for (int j = 0 ;j<len;j++){
                VectorXd v1(2);
                v1<<i,j;
                ma.row(ind) = v1;
                ind++;
        }   
    };
    ind = 0;
    vector<vector<int>> res;
    for (int i=0;i<ma.rows();i++){
        int num1 = ma(i,0);
        int num2 = ma(i,1);
        if (num1!=num2){
            vector<int> v1;
            v1.push_back(num1);
            v1.push_back(num2);
            sort(v1.begin(),v1.end());
            if (find(res.begin(),res.end(),v1)==res.end())
                res.push_back(v1);
        }
    }
    return res;
 }

任何提示或建议都会有所帮助。提前谢谢你。

Answer 1

STL 方式是使用std::next_permutation

std::vector<std::vector<int>> res;
std::vector<int> v(size - 2, 0);
v.resize(size, 1); // vector you be sorted at start : here {0, .., 0, 1, 1}.
do {
     res.push_back(v);
} while (std::next_permutation(v.begin(), v.end()));

Live example .

正如 Matthieu M 指出的那样，直接在 do while 循环中完成工作会更有效率。