我有几个数据看起来像这样:
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;
}
您可以像里程表一样实现它,这会导致以下结果(适用于不同大小的向量):
假设数组 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];
}
}
If you're interested in complexity, the number of iterator increments that get performed is easy to calculate. For simplicity here I'll assume each vector is the same length N. The total number of combinations is NK. The last iterator gets incremented each time, so that is NK, and moving back through the iterators this count gets divided by N each time, so we have NK + NK-1 + ... N1; this sum equals N(NK - 1)/(N-1) = O(NK). This also means that the amortized cost per-combination is O(1).
无论如何,简而言之,将其视为旋转数字轮的里程表。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)