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

Question

我需要有几个子向量的组合。for我试图用两个循环来做，但我认为我需要递归。主要问题是我正在使用向量向量，因此互联网上的大多数答案都不适用于我的情况。

我所拥有的是一个带有多个子向量的向量，类似于：

std::vector<std::vector<std::vector<int>>> x = {{{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}},...}

以下是上述示例所需的所有输出： {{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}}

如果我的向量的大小是 3 并且我的子向量的大小也是 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}} ...

我的向量/子向量的任何大小也是如此

标签： c++c++11

Answer 1

创建vi以 {0, 0, 0, ...} 开头的索引向量。在一个循环中，您将元素 push_backx[i][vi[i]]放入一个临时向量和 increment 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}}