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

https://stackoverflow.com/questions/1700079

19-09-2019
|

Вопрос

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

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

Решение

Это поможет:

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

Другие советы

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

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

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

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

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

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

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

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

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

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

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

Поскольку вы, кажется, хотите, чтобы каждый результат имел длину отдельных векторов, и вы, кажется, знаете, что каждый вектор имеет ширину 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, "");
}

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow