Most efficient way to get all permutations in c++

Question

I am trying to calculate a lot of combinations in C++. I came up with the following implement by myself, but its efficiency is not satisfactory. It takes more than 3 seconds to get C-18-2 (every 2 combination of 18), I believe this can be done in much less time.

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

Any hints or advise will be helpful. Thank you in advance.

Jarod42 · Accepted Answer · 2014-08-07 10:04:14Z

The stl way is to use 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.

As Matthieu M pointed out, it would be more efficient to do the works directly inside the do while loop.

I would point out that, if possible, it would be better to use this iteratively (ie, do the work inside do/while) rather than first generating and then consuming. It would obviate the need for res which may end up taking a lot of memory.

Jarod42 · Accepted Answer · 2014-08-07 12:00:15Z

A simpler way as you use combination of 2 elements, you may use a double loop:

std::vector<std::vector<int>> res; for (std::size_t i = 0; i != size; ++i) { for (std::size_t j = i + 1; j != size; ++j) { std::vector<int> v(size); v[i] = 1; v[j] = 1; res.push_back(v); } }

Collectives™ on Stack Overflow

Most efficient way to get all permutations in c++

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related