Howto إنشاء مجموعات من العديد من المتجهات دون حلقات تصلب في C ++؟

Question

لدي العديد من البيانات التي تبدو وكأنها:

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

المشكلة التي أواجهها الآن هي أن قانون الألغام التالي يفعل ذلك بواسطة Hardcoding الحلقات. نظرا لأن عدد المتجهات يمكن أن تختلف، نحتاج إلى وسيلة مرنة للحصول على نفس النتيجة. هل هنالك أي؟

يمكن أن يتعامل رمز الألغام هذا فقط التعامل مع ما يصل إلى 3 ناقلات (Hardcoded):

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

Answer 1

هذا وسوف تفعل خدعة:

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

Answer 2

يمكنك تنفيذ هذا مثل عداد المسافات، مما يؤدي إلى ما يلي (يعمل لنوع ناقلات مختلفة):

قل لديك ناقلات K في الصفيف الخامس: v[0], v[1], ... v[K-1]

الحفاظ على مجموعة من المحفوثة it (الحجم ك) في متجاولك، بدءا من 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.^K-1. + ... N.¹; ؛ هذا المبلغ يساوي ن (ن^ك - 1) / (N-1) = O (N^ك). هذا يعني أيضا أن التكلفة المطفأة لكل مزيج هو O (1).

على أي حال، باختصار، علاجها مثل عداد المسافات غزل عجلاتها المكونة من رقمها.

Answer 3

حل C ++ 0x. المقدمة، بطبيعة الحال، دعم الخاص بك التي تم تجميعها (حاليا GCC 4.5 و VS2010، وأعتقد).

الكملية التالية وتعمل مع دول مجلس التعاون الخليجي باستخدام -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;
}

Answer 4

الصعوبة الأساسية مع Recursion هنا هي أنك تحتاج إلى تتبع قائمة المؤشرات بأكملها (أو قم بإنشاء السلسلة بشكل تدريجي، حيث يشير سؤال آخر).

طريقة عرضية للتعامل مع هذه المشكلة دون إنشاء كائنات إضافية داخل الحلقات هي تسليم دالة المكاكسة الخاصة بك متجهات من المؤشرات، من نفس الطول مثل ناقل ناقلات:

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

Answer 5

الجمع بين ثلاثة ناقلات هي نفسها في الأساس تقريبا الجمع بين متجهين، ثم الجمع بين الثالث مع النتيجة.

لذلك كل ذلك يتلخص لكتابة وظيفة يمكن أن تجمع بين متجهين.

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 ++" لاستخدام المدخلات والمخرجات الإخراج ISO تمرير ناقلات حولها، وأكثر كفاءة بكثير. في الإصدار أعلاه، يتم نسخ المتجه مرارا وتكرارا ...

أنا ببساطة استخدمت ناقلات البقاء أقرب إلى التعليمات البرمجية الأصلية، ونأمل أن يكون هناك معنى أكبر لك.

Answer 6

نظرا لأنك تريد أن تكون كل إخراج طول ناقلات فردية، ويبدو أنك تعرف أن كل متجه هو 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]);
            }
        }
    }
}

Answer 7

أنا أيضا مهتم ببناء نوع من السهل شطف وتكرر الفرامل. أنا على دراية نهج نوع المسافات مدفوعة، إذا كنت سوف، حيث لديك مؤشرات المشي. شيء على طول تلك الخطوط. النقطة هي، لبناء tuples بسهولة عبر مجموعة تعسفية من المتجهات غير المرتبطة.

هذا لا يجيب على سؤالك تماما، ولا أعتقد، ولكن يمكنك بناء مجموعات زمنية ثابتة / تصميم باستخدام إنتاج المتغيرات مثل ما يلي، حيث 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, ...);

كما قلت، هذا هو دراسة وقت التصميم. إنه لا يبني tuples عبر مجموعة أوقات تشغيل من المتجهات. هذا هو الجانب السفلي. ومع ذلك، فإن الجانب الأمريكي هو أنك تكسب تجميع الوقت الفهم من TUPLEPLE TUPLES الخاص بك.

مرة أخرى، ليس تماما ما أنت، أو حتى أنا، ولكن ربما يساعد على إشرار ردود فعل إيجابية.

Answer 8

لن يتعطل حل 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, "");
}

Answer 9

أبسط طريقة للنهج هذا هو استخدام العودية. ستكون الوظيفة حلقة واحدة فيها وسوف تسمي نفسها، ودمج نفسها بإخراج المكالمة العودية. بالطبع، يمكن تحويل العودية للتكرار إذا كنت قلقا بشأن مساحة المكدس، ولكن على الأقل كنقطة انطلاق، فإن الحل العودية ربما سيكون من الأسهل بالنسبة لك.

Answer 10

استخدام وظيفة next_permutation المنفذة في STD من STL