如何在C++中创建几个没有硬编码循环的向量组合？

Question

我有几个看起来像这样的数据:

Vector1_elements = T,C,A
Vector2_elements = C,G,A
Vector3_elements = C,G,T
..... up to ...
VectorK_elements = ...

#Note also that the member of each vector is always 3.

我想要做的是通过VectorK在Vector1中创建所有元素组合.因此最后我们希望得到这个输出(使用Vector1,2,3):

TCC
TCG
TCT
TGC
TGG
TGT
TAC
TAG
TAT
CCC
CCG
CCT
CGC
CGG
CGT
CAC
CAG
CAT
ACC
ACG
ACT
AGC
AGG
AGT
AAC
AAG
AAT

我现在遇到的问题是我的下面的代码通过硬编码循环来做到这一点.由于Vector的数量可以变化,我们需要一种灵活的方法来获得相同的结果.有没有？

我的这段代码最多只能处理3个矢量(硬编码):

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
using namespace std;


int main  ( int arg_count, char *arg_vec[] ) {

    vector <string> Vec1;
          Vec1.push_back("T");
          Vec1.push_back("C");
          Vec1.push_back("A");

    vector <string> Vec2;
          Vec2.push_back("C");
          Vec2.push_back("G");
          Vec2.push_back("A");

    vector <string> Vec3;
          Vec3.push_back("C");
          Vec3.push_back("G");
          Vec3.push_back("T");



     for (int i=0; i<Vec1.size(); i++) {
        for (int j=0; j<Vec2.size(); j++) {
            for (int k=0; k<Vec1.size(); k++) {
                cout << Vec1[i] << Vec2[i] << Vec3[k] << endl;
            }
        }
     }



    return 0;
}

Answer 1

您可以像里程表一样实现这一点,这会产生以下结果(适用于不同大小的矢量):

假设你在数组v中有K个向量: v[0], v[1], ... v[K-1]

将一个迭代器数组it(大小为K)保存到向量中,从it[i] = v[i].begin().继续it[K-1]循环递增.当任何迭代器碰到end()相应的向量时,你将它包装到begin()并递增前一个迭代器(所以当it[K-1]环绕时,你递增it[K-2]).这些增量可以"级联",因此您应该在循环中循环执行它们.当it[0]周围的包裹,你就大功告成了(所以你的循环条件可以是这样的while (it[0] != v[0].end())

把所有这些放在一起,完成工作的循环(在设置迭代器之后)应该是这样的:

while (it[0] != v[0].end()) {
  // process the pointed-to elements

  // the following increments the "odometer" by 1
  ++it[K-1];
  for (int i = K-1; (i > 0) && (it[i] == v[i].end()); --i) {
    it[i] = v[i].begin();
    ++it[i-1];
    }
  }

如果您对复杂性感兴趣,则可以轻松计算执行的迭代器增量数.为了简单起见这里我假定每个矢量是相同的长度N.组合的总数是N ^ķ.最后一个迭代器每次递增,因此它是N ^K,并且通过迭代器移回这个计数每次除以N,所以我们有N ^K + N ^K-1 + ... N ¹ ; 该和等于N(N ^K -1)/(N-1)= O(N ^K).这也意味着每个组合的摊余成本为O(1).

无论如何,简而言之,它就像一个旋转其数字轮的里程表.

Answer 2

这样就可以了:

void printAll(const vector<vector<string> > &allVecs, size_t vecIndex, string strSoFar)
{
    if (vecIndex >= allVecs.size())
    {
        cout << strSoFar << endl;
        return;
    }
    for (size_t i=0; i<allVecs[vecIndex].size(); i++)
        printAll(allVecs, vecIndex+1, strSoFar+allVecs[vecIndex][i]);
}

致电:

printAll(allVecs, 0, "");

Answer 3

一个C++ 0x解决方案.当然,只要你编译支持它(我认为目前是GCC 4.5和VS2010).

以下编译并使用-std=c++0x开关与GCC 4.5一起使用.使用可变参数模板可以组合任意数量的容器.我相信你可以提出一个更惯用的解决方案.

#include <vector>       
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>

typedef std::vector<std::string> myvec;

// Base case.
void combine2(const std::string &row) {
    std::cout << row << std::endl;
}

// Recursive variadic template core function.
template<class T0, class ...T>
void combine2(const std::string &row, const T0& cont0, T...cont_rest) {
    for (auto i = cont0.begin(); i != cont0.end(); ++i) {
        std::stringstream ss;
        ss << row << *i;
        combine2(ss.str(), cont_rest...);
    }
}

// The actual function to call.
template<class ...T>
void combine(T...containers) {
    combine2("", containers...);
}

int main() {
    myvec v1 = {"T", "C", "A"}, v2 = {"C", "G", "A"}, v3 = {"C", "G", "T"};

    combine(v1);
    combine(v1, v2);
    combine(v1, v2, v3);

    // Or even...
    std::vector<std::string> v4 = {"T", "C", "A"};
    std::vector<char> v5 = {'C', 'G', 'A'};
    std::vector<int> v6 = {1 ,2 ,3};

    combine(v4);
    combine(v4, v5);
    combine(v4, v5, v6);

    return 0;
}