在 C++ 中，遍历向量的所有 k 个元素

问题描述 投票：0回答：2

在 C++ 中，我有一个 

vector
的 
int
，这样每个元素都是一个 n 位整数。

我想知道遍历向量的所有不同 k 元素的最有效方法。即我想遍历向量的 k 个元素的所有组合。 “最好”的方法是什么？

当 k 固定且已知时，一种方法是使用嵌套 for 循环，如下所示，但这种方法并不是很好，不能扩展到更高的 k，而且可能不是最有效的。

Example1 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){
         //do something;
      }
   }
   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];
         //do something
      }
   }
   return 0;
}

我尝试使用 itertools 包（从 python 移植到 C++），但它在我的笔记本电脑上不起作用，还不确定为什么。所以我想将这种类型的代码扩展到任何 k.

c++ combinations
2个回答
1
投票

解决这个问题的或多或少的标准方法是使用选择器并在选择器上排列。

示例：假设您有一个包含五个元素的

std::vector
。然后你需要创建一个助手 
std::vector<bool> selector
并将 k 个元素设置为 true。对选择器进行排列，然后将数据复制到结果中，并将“true”对应的选择器复制到结果中：

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 . . .

另一个要求是要有不同的结果。我们将通过使用只能包含唯一值的

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

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

结果：

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

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

结果：

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
0
投票

这将适用于

k
的所有值：

  • 使用尺寸为
    std::vector<size_t> index
    的
    k
  • 用不同的索引初始化它
    0,1,2,3...
  • 将其视为基数
    vect.size()
    数字，即您通过递增最后一个元素获得下一个索引。当元素到达
    vect.size()
    时，您将转到下一个“数字”。

这实际上与用

vect.size()
数字以
k
为底数计数是一样的。在每次迭代中，所需的组合是

 for (auto i : index) { 
     std::cout << vect[i] << " ";
 }
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.