17

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

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

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

我的这段代码最多只能处理 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;
}
4

10 回答 10

16

您可以像里程表一样实现它，这会导致以下结果（适用于不同大小的向量）：

假设您在数组 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 K。最后一个迭代器每次都会递增，所以是 N K，并且通过迭代器，这个计数每次都除以 N，所以我们有 N K + N K-1 + ... N 1；这个总和等于 N(N K - 1)/(N-1) = O(N K )。这也意味着每个组合的摊销成本为 O(1)。

无论如何，简而言之，将其视为旋转数字轮的里程表。

于 2009-11-09T20:29:58.273 回答
13

这可以解决问题：

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, "");
于 2009-11-09T10:32:22.673 回答
5

C++0x 解决方案。当然，前提是您的编译支持它（我认为目前是 GCC 4.5 和 VS2010）。

以下使用-std=c++0xswitch 编译和使用 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;
}
于 2009-11-09T10:41:57.933 回答
3

这里递归的基本困难是您需要跟踪整个索引列表（或者增量构造字符串，正如另一个问题指出的那样）。

在不在循环内构造其他对象的情况下处理此问题的一种便捷方法是为您的递归函数提供一个索引向量，其长度与向量向量的长度相同：

void printcombos(const vector<vector<string> >&vec,vector<int>&index,int depth) {
  if(depth==index.length()) {
    for(int i=0; i<depth; ++i) {
      cout<<vec[i][index[i]];
    }
    cout<<endl;
  } else {
    const vector<string> &myvec= vec[depth];
    int mylength= myvec.length();
    for(int i=0; i<mylength; ++i) {
      index[depth]=i;
      printcombos(vec,index,depth+1);
    }
  }
}
于 2009-11-09T10:33:23.667 回答
2

我也对构建某种易于冲洗和重复的组合感兴趣。我熟悉里程表驱动型方法，如果你愿意的话，你有步行指数。类似的东西。关键是，在任意一组不相关的向量中轻松构建元组。

这并不能完全回答您的问题，我不认为，但是您可以使用如下的可变参数生成来构建静态/设计时间组合，其中 T1-3 是任意类型：

template<class V>
void push_back_tupled_combos(V& v) {
  // Variadic no-args no-op
}

template<class V, typename A, typename B, typename C, typename... Args>
void push_back_tupled_combos(V& v, A a, B b, C c, Args... args) {
    v.push_back({ a, b, c });
    push_back_tupled_combos(v, args...);
}

template<class V, typename... Args>
void push_back_tupled_combos(V& v, Args... args) {
}

假设你有一个看起来像这样的向量：

typedef vector<tuple<T1, T2, T3>> CombosVector;

CombosVector combos;

push_back_tupled_combos(combos
  , 1, 2, 3
  , 4, 5, 6
  , 7, 8, 9, ...);

就像我说的，这是设计时的考虑。它不会在向量的运行时间范围内构建元组。这是不利的一面。然而，好的一面是您获得了对向量元组的编译时理解。

再说一次，不是你甚至我所追求的，但也许它有助于激发积极的反馈。

于 2017-11-18T17:01:06.027 回答
1

组合三个向量与首先组合两个向量，然后将第三个向量与结果组合基本相同。

所以这一切都归结为编写一个可以组合两个向量的函数。

std::vector< std::string > combine(std::vector< std::string > const & inLhs, std::vector< std::string > const & inRhs) {
    std::vector< std::string > result;
    for (int i=0; i < inLhs.size(); ++i) {
        for (int j=0; j < inRhs.size(); ++j) {
            result.push_back(inLhs[i] + inRhs[j]);
        }
    }
    return result;
}

然后是这样的：

std::vector< std::string > result = combine(Vec1, Vec2);
result = combine(result, Vec3);

对于您需要组合的每个向量，依此类推。

请注意，使用输入和输出迭代器 iso 传递向量更像是“C++ 方式”，而且效率更高。在上面的版本中，向量被一遍又一遍地复制......

我只是使用向量来更接近您的原始代码，并希望对您更有意义。

于 2009-11-09T10:31:25.723 回答
1

由于您似乎希望每个输出都是单个向量的长度，并且您似乎知道每个向量的宽度为 3 个元素

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

在这里使用递归作为一般解决方案似乎有点矫枉过正。

您可以使用类似的东西：

typedef boost::array<std::string, 3> StrVec;
// basically your hardcoded version corrected (Vec2[j] not [i])
void printCombinations(const StrVec &Vec1,
                       const StrVec &Vec2,
                       const StrVec &Vec3) {
    for (int i=0; i<Vec1.size(); i++) {
        for (int j=0; j<Vec2.size(); j++) {
            for (int k=0; k<Vec3.size(); k++) {
                std::cout << Vec1[i] << Vec2[j] << Vec3[k] << std::endl;
            }
        }
    }
}

void foo() {
    typedef std::vector<StrVec> StrVecLvl2;
    StrVecLvl2 vecs;

    // do whatever with it ...

    // iterate with index instead of iterator only to shorten the code
    for (int i = 0; i < vecs.size(); ++i) {
        for (int j = i+1; j < vecs.size(); ++j) {
            for (int k = j+1; k < vecs.size(); ++k) {
                printCombinations(vecs[i], vecs[j], vecs[k]);
            }
        }
    }
}
于 2009-11-09T12:42:13.187 回答
1

当向量大小不同时，上面的 printAll 解决方案将崩溃​​。

修复了该问题：

 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++)
    {
        if( i < allVecs[vecIndex].size() )
        {
            printAll(allVecs, vecIndex + 1, strSoFar + " " + allVecs[vecIndex][i]);
        }
    }
}

int main()
{
    vector <string> Vec1;
    Vec1.push_back("A1");
    Vec1.push_back("A2");
    Vec1.push_back("A3");
    Vec1.push_back("A4");

    vector <string> Vec2;
    Vec2.push_back("B1");
    Vec2.push_back("B2");

    vector <string> Vec3;
    Vec3.push_back("C1");

    vector<vector<string> > allVecs;
    allVecs.push_back(Vec3);
    allVecs.push_back(Vec1);
    allVecs.push_back(Vec2);

    printAll(allVecs, 0, "");
}
于 2019-07-09T11:52:11.087 回答
0

解决这个问题的最简单方法是使用递归。该函数将有一个循环，并将调用自身，将自身与递归调用的输出合并。当然，如果您担心堆栈空间，可以将递归转换为迭代，但至少作为一个起点，递归解决方案对您来说可能是最简单的。

于 2009-11-09T10:08:04.473 回答
-1

使用stl的std中实现的next_permutation函数

于 2009-11-09T12:04:03.690 回答