logo标签列表

如何在C++中创建多个向量的组合而不需要硬编码循环？

c++algorithmrecursionvectorcombinations
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.

我想做的是通过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

我现在遇到的问题是，我的以下代码通过硬编码循环来实现。由于向量数量可能会变化，我们需要一种灵活的方法来获得相同的结果。是否有这样的方法？
我的代码只能处理最多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;
}
你想如何处理重复项？例如第四个向量与第三个相同的情况下怎么办？此外，你的输入向量长度为3，但输出向量应该具有长度“k”（如果给定k个输入向量）？或者你还有其他决定从哪个输入向量中取哪些元素的方法吗？ - Dane
10个回答
16
你可以将其实现为一个类似于里程表的东西，这将导致以下结果（适用于不同大小的向量）：
假设你有一个包含K个向量的数组v：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。 总组合数为NK。 最后一个迭代器每次都会进行递增，因此它的值为NK；依次向前迭代器，每次该计数会除以N，因此我们有NK + NK-1 + ... N1；这个总和等于N(NK - 1)/(N-1) = O(NK)。 这也意味着每组合的平均摊销成本为O(1)。

总之，简而言之，将其视为一个里程表旋转其数字轮。

4
很高兴看到非递归的解决方案。 - BCS
如果你走另一条路，你可能可以内联“处理指向元素”的操作，这将改善复杂度常数，即 while (back != end) { ++it[0]; for (int i = 0; i < K; ++i) ... - jvdillon
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, "");
@interjay：谢谢。我该如何修改您的代码，使函数返回一个字符串而不是打印它？ - neversaint
1
你可以将字符串推入另一个vector<string>中，而不是直接打印。这个结果向量可以是全局变量，也可以作为引用传递给此函数。 - interjay
你的答案看起来非常优雅。我试图在我的问题中复制它，但不幸的是我无法做到。你能帮我吗：https://dev59.com/d2435IYBdhLWcg3wrSFB 谢谢。 - 0x0
很酷！我已经在我的Qt代码中使用它并发布了下面的变化。 - Valentin H
5
一份C++0x的解决方案。当然，前提是你的编译器支持它（目前GCC 4.5和VS2010应该支持）。
下面的代码使用可变参数模板，可以将任意数量的容器组合在一起，可以在GCC 4.5中使用-std=c++0x开关编译通过。我相信你可以想出更加惯用的解决方案。
#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;
}
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);
    }
  }
}
2

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

这并不完全回答你的问题，但你可以使用可变生产（variadic production）来构建静态/设计时组合，例如以下代码，其中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, ...);

就像我说的，这是一个设计时的考虑。它不会在运行时范围内构建元组。这是缺点。然而，好处是你可以在编译时理解你的向量元组。

再次强调，这并不完全是你或者我想要的，但也许它能激发有利的反馈。

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);

对于每个需要合并的向量，都要执行类似的操作。

请注意，使用输入和输出迭代器而不是传递向量更符合“C++方式”，并且更有效率。在上面的版本中，向量被反复复制...

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

1

由于您似乎希望每个输出都是单独向量的长度，并且您似乎知道每个向量始终有3个元素，因此使用递归来解决问题似乎有点过度。

#注意，每个向量的成员始终为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]);
            }
        }
    }
}
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, "");
}
0

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

-1
使用stl中实现的next_permutation函数。
1
next_permutation是将一个向量的组合值进行排列，而不是多个向量的组合值。 - Valentin H
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接