Подтвердить что ты не робот

Как создать комбинации нескольких векторов без контуров жесткого кодирования в С++?

У меня есть несколько данных, которые выглядят следующим образом:

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 векторов (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;
}
4b9b3361

ОТВЕТЫ

Ответ 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, "");

Ответ 2

Вы можете реализовать это как одометр, что приводит к следующему (работает для векторов разного размера):

Скажем, у вас есть векторы 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. Общее число комбинаций N K. Последний итератор увеличивается каждый раз, так что N K и, возвращаясь через итераторы, этот счет делится на N каждый раз, поэтому мы имеем N K + N K-1 +... N 1; эта сумма равна N (N K - 1)/(N-1) = O (N K). Это также означает, что амортизированная стоимость за комбинацию равна O (1).

Во всяком случае, короче говоря, рассматривайте его как одометр, вращающий его цифровые колеса.

Ответ 3

Решение С++ 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;
}

Ответ 4

Основная сложность с рекурсией здесь заключается в том, что вам нужно отслеживать весь список индексов (или строить строку поэтапно, как указывает другой вопрос).

Целесообразным способом решения этой проблемы без создания дополнительных объектов внутри циклов является передача вашей рекурсивной функции вектора индексов той же длины, что и вектор векторов:

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

Ответ 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);

и т.д. для каждого вектора, который вам нужен.

Обратите внимание, что это больше "С++ way" для использования итераторов ввода и вывода i.s.o. проходящие векторы вокруг, и намного более эффективные. В вышеприведенной версии вектор копируется снова и снова...

Я просто использовал векторы, чтобы оставаться ближе к вашему исходному коду и, надеюсь, имеет больше смысла для вас.

Ответ 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]);
            }
        }
    }
}

Ответ 7

Я тоже заинтересован в создании своего рода легкого ополаскивания и повторения комбинаторного. Я знаком с подходом, управляемым одометром, если хотите, где у вас есть ходячие индексы. Что-то в этом роде. Дело в том, что легко построить кортежи через произвольный набор несвязанных векторов.

Это не совсем ответит на ваш вопрос, я не думаю, но вы можете создавать статические/дизайнерские комбинации времени, используя вариационное производство, такое как следующее, где 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, ...);

Как я уже сказал, это время рассмотрения дизайна. Он не создает кортежи по диапазону векторов времени выполнения. Это нижняя сторона. Тем не менее, верхняя сторона заключается в том, что вы получаете время компиляции ваших векторных кортежей.

Опять же, не совсем то, что вы, или даже я, после, но, возможно, это помогает исправить благоприятную обратную связь.

Ответ 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, "");
}

Ответ 10

Использовать функцию next_permutation, реализованную в std stl