c++ - 如何得到几个子 vector 的组合？

Question

我需要几个子 vector 的组合。我尝试用两个 for 循环来完成它，但我认为我需要递归。主要问题是我正在处理 vector 的 vector ，因此互联网上的大多数答案都不适用于我的情况。

我有一个带有多个子 vector 的 vector ，类似这样的东西:

std::vector<std::vector<std::vector<int>>> x = {{{0,0},{1,1}},{{2,2},{3,3}},{{4,4},{5,5}}}

我期望的输出是一个包含所有可能组合的 vector ，如下所示:

{{{0,0},{2,2},{4,4}},{{0,0},{2,2},{5,5}},{{0,0},{3,3},{4,4}},{{0,0},{3,3},{5,5}},...}

下面是上面例子中我需要的所有输出: {{0,0},{2,2},{4,4}} {{0,0},{2,2},{5,5}} {{0,0},{3,3} ,{4,4}} {{0,0},{3,3},{5,5}} {{1,1},{2,2},{4,4}} {{1,1},{2,2},{5,5}} {{1,1},{3,3} ,{4,4}} {{1,1},{3,3},{5,5}}

如果我的 vector 的大小是 3，我的子 vector 的大小也是 3，如下所示:{{{0,0},{1,1},{2,2}},{{ 3,3},{4,4},{5,5}},{{6,6},{7,7},{8,8}}}

输出必须是:

{{0,0},{3,3},{6,6}} , {{0,0},{3,3},{7,7}} , {{0,0},{3,3},{8,8}} ,  {{0,0},{4,4},{6,6}} , {{0,0},{4,4},{7,7}} , {{0,0},{4,4},{8,8}} ...

我的 vector/子 vector 的任何大小都是如此

Answer 1

创建以 {0, 0, 0, ...} 开头的索引 vector vi。在一个循环中，您将元素 x[i][vi[i]] 推回一个临时 vector 并递增 vi。

您在循环中从后面递增 vi:如果 vi[i] 大于 x[i].size()你递增 vi[i - 1] ...

如果 vi 无法递增，则循环中断。

#include <iostream>
#include <vector>
using std::cout;
using std::ostream;
using std::size_t;
using std::vector;

ostream &operator<<(ostream &os, const vector<vector<vector<int>>> &vvec);
vector<vector<vector<int>>> combinations(const vector<vector<vector<int>>> &vvec);

int main() {
    vector<vector<vector<int>>> x = {{{0,0},{1,1}},{{2,2},{3,3}},{{4,4},{5,5}}};
    cout << combinations(x);
}

ostream &operator<<(ostream &os, const vector<vector<vector<int>>> &vvec) {
    bool first1 = true;
    for (const auto &v : vvec) {
        if (first1) first1 = false;
        else os << ' ';
        bool first2 = true;
        os << '{';
        for (const auto &el : v) {
            if (first2) first2 = false;
            else os << ',';
            os << '{' << el[0] << ',' << el[1] << '}';
        }
        os << '}';
    }
    return os;
}

vector<vector<vector<int>>> combinations(const vector<vector<vector<int>>> &x) {
    vector<size_t> vectorOfIndexes(x.size());
    vector<vector<vector<int>>> resultVector;
    bool finished = false;
    while (!finished) {
        vector<std::vector<int>> combination;
        for (size_t i{0}; i < vectorOfIndexes.size(); ++i) {
            combination.push_back(x[i][vectorOfIndexes[i]]);
        }
        resultVector.push_back(combination);
        for (size_t i {0}; i < vectorOfIndexes.size(); ++i) {
            ++vectorOfIndexes[vectorOfIndexes.size() - i - 1];
            if (vectorOfIndexes[vectorOfIndexes.size() - i - 1] >= x[x.size() - i - 1].size()) {
                vectorOfIndexes[vectorOfIndexes.size() - i - 1] = 0;
                if (i == vectorOfIndexes.size() - 1) finished = true;
            } else {
                break;
            }
        }
    }
    return resultVector;
}

输入:

{{{0,0},{1,1}},{{2,2},{3,3}},{{4,4},{5,5}}}

输出:

{{0,0},{2,2},{4,4}} {{0,0},{2,2},{5,5}} {{0,0},{3,3},{4,4}} {{0,0},{3,3},{5,5}} {{1,1},{2,2},{4,4}} {{1,1},{2,2},{5,5}} {{1,1},{3,3},{4,4}} {{1,1},{3,3},{5,5}}

输入:

{{{0,0},{1,1},{2,2}},{{3,3},{4,4},{5,5}},{{6,6},{7,7},{8,8}},{{9,9},{10,10},{11,11}}}

输出:

{{0,0},{3,3},{6,6},{9,9}} {{0,0},{3,3},{6,6},{10,10}} {{0,0},{3,3},{6,6},{11,11}} {{0,0},{3,3},{7,7},{9,9}} {{0,0},{3,3},{7,7},{10,10}} {{0,0},{3,3},{7,7},{11,11}} {{0,0},{3,3},{8,8},{9,9}} {{0,0},{3,3},{8,8},{10,10}} {{0,0},{3,3},{8,8},{11,11}} {{0,0},{4,4},{6,6},{9,9}} {{0,0},{4,4},{6,6},{10,10}} {{0,0},{4,4},{6,6},{11,11}} {{0,0},{4,4},{7,7},{9,9}} {{0,0},{4,4},{7,7},{10,10}} {{0,0},{4,4},{7,7},{11,11}} {{0,0},{4,4},{8,8},{9,9}} {{0,0},{4,4},{8,8},{10,10}} {{0,0},{4,4},{8,8},{11,11}} {{0,0},{5,5},{6,6},{9,9}} {{0,0},{5,5},{6,6},{10,10}} {{0,0},{5,5},{6,6},{11,11}} {{0,0},{5,5},{7,7},{9,9}} {{0,0},{5,5},{7,7},{10,10}} {{0,0},{5,5},{7,7},{11,11}} {{0,0},{5,5},{8,8},{9,9}} {{0,0},{5,5},{8,8},{10,10}} {{0,0},{5,5},{8,8},{11,11}} {{1,1},{3,3},{6,6},{9,9}} {{1,1},{3,3},{6,6},{10,10}} {{1,1},{3,3},{6,6},{11,11}} {{1,1},{3,3},{7,7},{9,9}} {{1,1},{3,3},{7,7},{10,10}} {{1,1},{3,3},{7,7},{11,11}} {{1,1},{3,3},{8,8},{9,9}} {{1,1},{3,3},{8,8},{10,10}} {{1,1},{3,3},{8,8},{11,11}} {{1,1},{4,4},{6,6},{9,9}} {{1,1},{4,4},{6,6},{10,10}} {{1,1},{4,4},{6,6},{11,11}} {{1,1},{4,4},{7,7},{9,9}} {{1,1},{4,4},{7,7},{10,10}} {{1,1},{4,4},{7,7},{11,11}} {{1,1},{4,4},{8,8},{9,9}} {{1,1},{4,4},{8,8},{10,10}} {{1,1},{4,4},{8,8},{11,11}} {{1,1},{5,5},{6,6},{9,9}} {{1,1},{5,5},{6,6},{10,10}} {{1,1},{5,5},{6,6},{11,11}} {{1,1},{5,5},{7,7},{9,9}} {{1,1},{5,5},{7,7},{10,10}} {{1,1},{5,5},{7,7},{11,11}} {{1,1},{5,5},{8,8},{9,9}} {{1,1},{5,5},{8,8},{10,10}} {{1,1},{5,5},{8,8},{11,11}} {{2,2},{3,3},{6,6},{9,9}} {{2,2},{3,3},{6,6},{10,10}} {{2,2},{3,3},{6,6},{11,11}} {{2,2},{3,3},{7,7},{9,9}} {{2,2},{3,3},{7,7},{10,10}} {{2,2},{3,3},{7,7},{11,11}} {{2,2},{3,3},{8,8},{9,9}} {{2,2},{3,3},{8,8},{10,10}} {{2,2},{3,3},{8,8},{11,11}} {{2,2},{4,4},{6,6},{9,9}} {{2,2},{4,4},{6,6},{10,10}} {{2,2},{4,4},{6,6},{11,11}} {{2,2},{4,4},{7,7},{9,9}} {{2,2},{4,4},{7,7},{10,10}} {{2,2},{4,4},{7,7},{11,11}} {{2,2},{4,4},{8,8},{9,9}} {{2,2},{4,4},{8,8},{10,10}} {{2,2},{4,4},{8,8},{11,11}} {{2,2},{5,5},{6,6},{9,9}} {{2,2},{5,5},{6,6},{10,10}} {{2,2},{5,5},{6,6},{11,11}} {{2,2},{5,5},{7,7},{9,9}} {{2,2},{5,5},{7,7},{10,10}} {{2,2},{5,5},{7,7},{11,11}} {{2,2},{5,5},{8,8},{9,9}} {{2,2},{5,5},{8,8},{10,10}} {{2,2},{5,5},{8,8},{11,11}}