HOWTO创建没有C ++硬编码循环数矢量的组合？

StackOverflow https://stackoverflow.com/questions/1700079

题

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

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在向量1元素的所有组合。 因此，在结束时，我们希望得到这个输出（使用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;
}
有帮助吗？

解决方案

这将达到目的：

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

其他提示

可以实现这样的里程计，这导致下述的（作品不同大小的矢量）：

假设有在数组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 ķ，和向后移动通过所述迭代该计数得到由每个时间N分割，所以我们有N ķ + N K-1 + ... N 1 ;这个总和等于N（N ķ - 1）/（N-1）= O（N ķ）。这也意味着，每个组合中的摊销成本是O（1）。

不管怎样，在短，把它当作一个里程表纺丝其位轮。

一个的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;
}

与递归这里的基本困难是，你需要跟踪指数的整个列表中（或者逐步构建字符串，作为另一个问题指出）。

，而不构成环内另外的对象来处理这个问题的一个权宜的方法是手的递归函数索引的向量，相同的长度向量的向量的：

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

结合三个矢量基本上相同第一结合两个向量，然后组合第三与一个结果。

因此，一切都归结为编写可以结合两个向量的函数。

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 ++方法”，使用输入和输出迭代I.S.O.周围路过的载体和有效得多。另外，在上述版本向量被复制遍地...

我只是用向量更贴近您的原代码，并希望更有意义给你。

因为你似乎希望每个输出是单独的矢量的长度，并且你似乎知道，每个矢量是宽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]);
            }
        }
    }
}

我也很感兴趣，建立某种易于冲洗和重复组合。我所熟悉的里程表驱动型的方法，如果你愿意，当你有走索引。类似的规定。问题的关键是，跨越无关矢量的任意集合，以方便地构建出元组。

这并不完全回答你的问题，我不觉得，但是你可以建立使用可变参数的生产，如以下，其中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, ...);

就像我说，这是一个设计考虑时间。它不建立跨载体的运行时间范围内的元组。这是不利的一面。向上的一面，然而，就是你获得编译矢量元组的时间理解。

再次不太你，甚至我所追求的，但也许它有助于激发良好的反馈。

以上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, "");
}

解决这个最简单的方法是使用递归。该功能将在这一个循环，并调用自身，用递归调用的输出合并本身。当然，递归可以转换，如果你担心的堆栈空间进行迭代，但至少作为一个起点，递归的解决方案将可能是最简单的你。

使用在STL的STD实现next_permutation功能

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top