Как создать комбинации нескольких векторов без циклов жесткого кодирования в 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

Проблема, с которой я столкнулся сейчас, заключается в том, что мой следующий код делает это путем жесткого кодирования циклов. Поскольку число векторов может варьироваться, нам нужен гибкий способ получить тот же результат. Есть ли?

Этот мой код может обрабатывать только до 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;
}

Answer 1

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

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

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

Answer 2

Это поможет:

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 3

C ++ 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;
}

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

Answer 5

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

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

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

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

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

Объединение трех векторов, по сути, аналогично тому, как сначала объединить два вектора, а затем объединить третий с результатом.

Итак, все сводится к написанию функции, которая может объединять два вектора.

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. Передача векторов вокруг, и гораздо эффективнее. В вышеуказанной версии вектор копируется снова и снова ...

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

Answer 8

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

Answer 9

Самый простой способ подойти к этому - использовать рекурсию. Функция будет иметь один цикл и будет вызывать себя, сливаясь с выходом рекурсивного вызова. Конечно, рекурсию можно преобразовать в итерацию, если вы беспокоитесь о стековом пространстве, но, по крайней мере, в качестве отправной точки, рекурсивное решение, вероятно, будет для вас наиболее простым.