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

У меня есть несколько данных, которые выглядят так:

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  #include  #include  #include  using namespace std; int main ( int arg_count, char *arg_vec[] ) { vector  Vec1; Vec1.push_back("T"); Vec1.push_back("C"); Vec1.push_back("A"); vector  Vec2; Vec2.push_back("C"); Vec2.push_back("G"); Vec2.push_back("A"); vector  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 > &allVecs, size_t vecIndex, string strSoFar) { if (vecIndex >= allVecs.size()) { cout << strSoFar << endl; return; } for (size_t i=0; i 

Позвоните:

 printAll(allVecs, 0, ""); 

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

Скажем, у вас есть векторы K в массиве v: v[0], v[1], ... v[K-1]

Сохраните массив iteratorов (размер K) в ваши векторы, начиная с it[i] = v[i].begin() . Продолжайте увеличивать it[K-1] в цикле. Когда любой iterator попадает в end() соответствующего вектора, вы завертываете его для begin() и увеличиваете и предыдущий iterator (так, когда it[K-1] обертывается, вы увеличиваете it[K-2] ). Эти приращения могут «каскадироваться», поэтому вы должны делать их в цикле назад. Когда it[0] обертывается, вы закончили (так что ваше условие цикла может быть чем-то вроде while (it[0] != v[0].end())

Объединяя все это, цикл, который выполняет работу (после настройки iteratorов), должен выглядеть примерно так:

 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]; } } , 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]; } } 

Если вас интересует сложность, количество шагов iteratorа, которое выполняется, легко вычислить. Для простоты здесь я предполагаю, что каждый вектор имеет одинаковую длину N. Общее число комбинаций равно N K. Последний iterator увеличивается каждый раз, так что это N K , и, возвращаясь через iteratorы, этот счет делится на 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, я думаю).

Следующий компилируется и работает с GCC 4.5 с помощью -std=c++0x . Использование вариативных шаблонов позволяет комбинировать произвольное количество контейнеров. Я уверен, что вы можете придумать более идиоматическое решение.

 #include  #include  #include  #include  #include  typedef std::vector myvec; // Base case. void combine2(const std::string &row) { std::cout << row << std::endl; } // Recursive variadic template core function. template 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 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 v4 = {"T", "C", "A"}; std::vector v5 = {'C', 'G', 'A'}; std::vector v6 = {1 ,2 ,3}; combine(v4); combine(v4, v5); combine(v4, v5, v6); return 0; } 

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

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

 void printcombos(const vector >&vec,vector&index,int depth) { if(depth==index.length()) { for(int i=0; i &myvec= vec[depth]; int mylength= myvec.length(); for(int i=0; i 

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

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

 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 ++-путь» для использования iteratorов ввода и вывода, проходящих через векторы, и намного более эффективных. В вышеприведенной версии вектор копируется снова и снова ...

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

Поскольку вы, кажется, хотите, чтобы каждый результат был длиной отдельных векторов, и вы, кажется, знаете, что каждый вектор имеет 3 элемента в ширину от

#Note also that the member of each vector is always 3.

использование рекурсии для общего решения кажется немного излишним здесь.

Вы можете использовать что-то вроде этого:

 typedef boost::array 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 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 void push_back_tupled_combos(V& v) { // Variadic no-args no-op } template 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 void push_back_tupled_combos(V& v, Args... args) { } 

Предполагая, что у вас есть вектор, который выглядит примерно так:

 typedef vector> CombosVector; CombosVector combos; push_back_tupled_combos(combos , 1, 2, 3 , 4, 5, 6 , 7, 8, 9, ...); 

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

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

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

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

  • Реализация prologа
  • Рекурсивно перечислять файлы в Java
  • найти все подмножества, которые суммируются с определенным значением
  • Является ли рекурсивный-итеративный метод лучше, чем чисто итеративный метод, чтобы выяснить, является ли число простым?
  • Значения, полученные в случае рекурсивной функции
  • Ограничивает ли recursion глубину C ++?
  • Понимание того, как работают рекурсивные функции
  • Заголовки, включающие друг друга в C ++
  • Рекурсия хвоста в C ++
  • Рекурсивная анонимная функция Matlab
  • Является ли законным возвращаться в main () на C ++?
  • Давайте будем гением компьютера.