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

Это поможет:

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

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

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

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

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

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

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

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

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

Обратите внимание, что это больше «способ С++» для использования итераторов ввода и вывода 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]);
            }
        }
    }
}

Приведенное выше решение 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, реализованную в std из stl