C ++でのハードコーディングループせずに、いくつかのベクトルの組み合わせを作成するにはどのように？
https://stackoverflow.com/questions/1700079
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私はこのようになりますいくつかのデータを持っています
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を通じてベクトル2内のすべての要素の組み合わせを作成することです。 そこで最後に、私たちは、この出力（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で始まる、あなたのベクターにイテレータのit[i] = v[i].begin()（サイズK）の配列をしてください。ループ内で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 であると仮定します。最後のイテレータはそれが K Nであるので、たびに増加し、このカウントはNずつ分けますイテレータを通じて戻って移動するので、我々はN K + Nを持っています K-1 + ... N 1 。この和がNに等しい（N K - 1）/（N-1）= O（N K ）。これはまた当たり組み合わせ償却コストは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);
}
}
}
3つのベクトルを組み合わせることは、本質的に最初の二つのベクトルを合成し、その結果と第三のいずれかの組み合わせと同じである。
だから、すべての2つのベクトルを組み合わせることができます関数を書くに沸くます。
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);
とその上のすべてのベクトルのためにあなたが結合する必要はあります。
これは、入力と出力イテレータのi.s.o.を使用するために、「C ++の道」よりだということに注意してください周りのベクトルを渡すと、はるかに効率的。上記のバージョンでは、ベクターは、コピーされ及びますオーバー...
私は単にあなたの元のコードに近い滞在し、うまくいけば、あなたに多くの意味をなすためにベクトルを使用します。
あなたは、各出力は、個々のベクトルの長さで欲しいように見える、とあなたは、各ベクトルは、
から広い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, "");
}
このアプローチする最も簡単な方法は、再帰を使用することです。関数は1つのループを持つことになりますし、再帰呼び出しの出力を使用して自身をマージ、自分自身を呼び出します。もちろん、再帰を使用すると、スタック領域心配している場合は反復に変換することができますが、少なくとも出発点として、再帰的な解決策は、おそらくあなたのために最も簡単になります。
STLのSTDに実装next_permutation関数を使用してください。
