英文:
in C++, looping through all k elements of a vector
问题
在C++中，我有一个存储n位整数的int类型的vector。我想知道循环遍历该向量中所有不同的k个元素的最有效方法。也就是说，我想要循环遍历该向量中所有k个元素的组合。什么是最好的方法？
当k固定已知时，一种方法是使用嵌套的for循环，如下所示，但这种方法不是特别好，对于更大的k不可扩展，而且可能不是最有效的方法。
例1，k=2，使用两个嵌套的for循环。
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vect={1,8,9,10};
for (int i:vect){
for (int j:vect){
//执行某些操作;
}
}
return 0;
}
例2：利用元素是不同的事实，我可以通过索引循环，当向量很大时可以加快速度。
#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];
//执行某些操作
}
}
return 0;
}
我尝试使用itertools库（从Python移植到C++），但它在我的笔记本电脑上无法运行，还不清楚原因。所以我想将这种类型的代码扩展到任何k。
英文:
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.
答案1
得分: 2
以下是代码部分的翻译：
解决这个问题的一种更或多的标准方法是使用选择器并在选择器上进行排列。
示例：假设您有一个带有五个元素的 `std::vector`。然后您需要创建一个辅助的 `std::vector<bool> selector` 并将 k 个元素设置为 true。对选择器进行排列，然后将数据复制，将“true”对应的选择器复制到结果中：
5 个值：k= 2
值 1 2 3 4 5
选择器 0 0 0 1 1
存储选择的数据 4 和 5。
获取选择器的下一个排列
值 1 2 3 4 5
选择器 0 0 1 0 1
存储选择的数据 3 和 5。
获取选择器的下一个排列
值 1 2 3 4 5
选择器 0 0 1 1 0
存储选择的数据 3 和 4。
获取选择器的下一个排列
值 1 2 3 4 5
选择器 0 1 0 0 1
存储选择的数据 2 和 5。
获取选择器的下一个排列 . . .
以此类推 . . .
还有一个附加要求，即要获得不同的结果。我们将使用 `std::set` 来实现这一点，它只能包含唯一的值。
这个实现非常直观和易于理解。请参阅以下示例：
#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{};
// 创建选择器数组
std::vector<bool> selector(v.size(), false);
// 将选择器数组中的 k 个元素设置为 true
std::fill(selector.begin(), std::next(selector.begin(), k), true);
// 现在我们将对选择器进行所有的排列
do {
// 临时存储一个组选择的数据
std::set<int> group{};
// 如果相应的选择器被设置，将数据复制到组中
std::copy_if(v.begin(), v.end(), std::inserter(group,group.begin()), [&, k = 0u](int i)mutable { return selector[k++]; });
// 仅存储具有所需大小 k 的数据
if (group.size() == k)
result.insert(group);
} while (std::prev_permutation(selector.begin(), selector.end()));
return result;
}
// 对所有可能的 k 进行测试的代码
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';
}
}
}
结果：
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
如果您还希望有重复的值，那么可以将 std::set 替换为 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{};
// 创建选择器数组
std::vector<bool> selector(v.size(), false);
// 将选择器数组中的 k 个元素设置为 true
std::fill(selector.begin(), std::next(selector.begin(), k), true);
// 现在我们将对选择器进行所有的排列
do {
// 临时存储一个组选择的数据
std::vector<int> group{};
// 如果相应的选择器被设置，将数据复制到组中
std::copy_if(v.begin(), v.end(), std::back_inserter(group), [&, k = 0u](int i)mutable { return selector[k++]; });
// 存储具有所需大小 k 的数据
result.insert(group);
} while (std::prev_permutation(selector.begin(), selector.end()));
return 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
<details>
<summary>英文:</summary>
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:
```TXT
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
答案2
得分: -1
这将适用于所有k的值：
- 使用大小为
k的std::vector<size_t> index - 用不同的索引
0,1,2,3...来初始化它 - 将其视为基数为
vect.size()的数字，也就是通过增加最后一个元素来获得下一个索引。当元素达到vect.size()时，将进位到下一个“数字”。
这实际上与使用k位在基数为vect.size()中计数是一样的。在每次迭代中，所需的组合是：
for (auto i : index) {
std::cout << vect[i] << " ";
}
英文:
This will work for all values of k:
- use a
std::vector<size_t> indexof sizek - initialize it with distinct indices
0,1,2,3... - treat it as a base-
vect.size()number, ie you get the next index by incrementing the last element. When the element reachesvect.size()you carry over to the next "digit".
It is really the same as counting in base vect.size() with k digits. In each iteration the desired combination is
for (auto i : index) {
std::cout << vect[i] << " ";
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论