c++ - 如何在 C++ 中创建没有硬编码循环的多个 vector 的组合？

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.

我想要做的是创建 Vector1 到 VectorK 中的所有元素组合。 因此最终我们希望得到这个输出(使用 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 个 vector (硬编码):

#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

您可以像里程表一样实现它，这会导致以下结果(适用于不同大小的 vector ):

假设数组 v 中有 K 个 vector :v[0], v[1], ... v[K-1]

将迭代器数组 it(大小 K)保存到 vector 中，从 it[i] = v[i].begin() 开始。在循环中不断增加 it[K-1]。当任何迭代器命中相应 vector 的 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];
    }
  }

如果您对复杂性感兴趣，那么执行的迭代器增量的数量很容易计算。为简单起见，我假设每个 vector 的长度为 N。组合的总数为 N^K。最后一个迭代器每次都递增，所以是 N^K，并且通过迭代器，这个计数每次都除以 N，所以我们有 N^K + N ^K-1 + ... N¹;这个总和等于 N(N^K - 1)/(N-1) = O(N^K)。这也意味着每个组合的摊销成本为 O(1)。

总之，把它当作一个转动数字轮子的里程表。