In C++, I have a vector of int, such that each element is a n-bits integer.
I would like to know the most efficient way to loop through all distinct k elements of the vector. i.e. I want to loop through all combinations of k elements of my vector. What is the 'best' way to do it ?
When k is fixed and know, one way to do it is with nested for loops, as below, but the approach is not really nice, not scalable to higher k, and probably not the most efficient.
Example1 with k=2, using two nested for loops.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vect={1,8,9,10};
for (int i:vect){
for (int j:vect){
//do something;
}
}
return 0;
}
Example2: Using the fact that the element are distinct, I can loop through indices, and make it much faster when the vector is large.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vect={1,8,9,10};
size_t vect_size = vect.size();
for (size_t a = 0; a != vect_size ; a++) {
for (size_t b = a+1; b != vect_size ; b++) {
i = vect[a];
j = vect[b];
//do something
}
}
return 0;
}
I tried to use the itertools package (ported from python to C++), but it's not working on my laptop, not sure why yet. So I would like to scale that type of code to any k.
The more or less standard approach to solve this problem is to use a selector and permute over the selector.
Example: Assume, you have a std::vector with five elements. Then you need to create a helper std::vector<bool> selector and set k elements to true. Do a permutation over the selector and then copy the data, with a "true" corresponding selector into the result:
5 Values: k= 2
Values 1 2 3 4 5
Selector 0 0 0 1 1
Store selected data 4 and 5.
Get next permutation for selector
Values 1 2 3 4 5
Selector 0 0 1 0 1
Store selected data 3 and 5.
Get next permutation for selector
Values 1 2 3 4 5
Selector 0 0 1 1 0
Store selected data 3 and 4.
Get next permutation for selector
Values 1 2 3 4 5
Selector 0 1 0 0 1
Store selected data 2 and 5.
Get next permutation for selector . . .
And so on and so on . . .
An additional requirement was to have distinct results. We will achieve this by using a std::set which can hold only unique values.
The implementation is the straight forward and easy to understand. Please see the below example:
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
std::set<std::set<int>> getCombinations(const std::vector<int>& v, int k) {
std::set<std::set<int>> result{};
// Create the selector array
std::vector<bool> selector(v.size(), false);
// Set k elements in the selector array to true
std::fill(selector.begin(), std::next(selector.begin(), k), true);
// Now we will do all permutations of the selector
do {
// Temporary, to store one group of selected data
std::set<int> group{};
// Copy data into group, if corresponding selector is set
std::copy_if(v.begin(), v.end(), std::inserter(group,group.begin()), [&, k = 0u](int i)mutable { return selector[k++]; });
// Only store data, with the requested size of k
if (group.size() == k)
result.insert(group);
} while (std::prev_permutation(selector.begin(), selector.end()));
return result;
}
// Test code for all possible ks
int main() {
std::vector data{ 1,2,3,3,3,4,5 };
for (int k = 1; k <= data.size(); ++k) {
auto combinations = getCombinations(data, k);
std::cout << "\n\nFor k = " << k << "\n";
for (const auto& v : combinations) {
for (const int i : v) std::cout << i << ' ';
std::cout << '\n';
}
}
}
Result:
For k = 1
1
2
3
4
5
For k = 2
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
For k = 3
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
For k = 4
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5
For k = 5
1 2 3 4 5
For k = 6
For k = 7
IF you also want to have duplicated vales, then replace the std::set with a std::vector
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
std::set<std::vector<int>> getCombinations(const std::vector<int>& v, int k) {
std::set<std::vector<int>> result{};
// Create the selector array
std::vector<bool> selector(v.size(), false);
// Set k elements in the selector array to true
std::fill(selector.begin(), std::next(selector.begin(), k), true);
// Now we will do all permutations of the selector
do {
// Temporary, to store one group of selected data
std::vector<int> group{};
// Copy data into group, if corresponding selector is set
std::copy_if(v.begin(), v.end(), std::back_inserter(group), [&, k = 0u](int i)mutable { return selector[k++]; });
// store data, with the requested size of k
result.insert(group);
} while (std::prev_permutation(selector.begin(), selector.end()));
return result;
}
Result:
For k = 1
1
2
3
4
5
For k = 2
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 3
3 4
3 5
4 5
For k = 3
1 2 3
1 2 4
1 2 5
1 3 3
1 3 4
1 3 5
1 4 5
2 3 3
2 3 4
2 3 5
2 4 5
3 3 3
3 3 4
3 3 5
3 4 5
For k = 4
1 2 3 3
1 2 3 4
1 2 3 5
1 2 4 5
1 3 3 3
1 3 3 4
1 3 3 5
1 3 4 5
2 3 3 3
2 3 3 4
2 3 3 5
2 3 4 5
3 3 3 4
3 3 3 5
3 3 4 5
For k = 5
1 2 3 3 3
1 2 3 3 4
1 2 3 3 5
1 2 3 4 5
1 3 3 3 4
1 3 3 3 5
1 3 3 4 5
2 3 3 3 4
2 3 3 3 5
2 3 3 4 5
3 3 3 4 5
For k = 6
1 2 3 3 3 4
1 2 3 3 3 5
1 2 3 3 4 5
1 3 3 3 4 5
2 3 3 3 4 5
For k = 7
1 2 3 3 3 4 5