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

Question

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

Сообщение об ошибке, которое я получал, было похоже, но причина в том, что срок действия подписанного сертификата уже истек. Когда клиент openssl был предпринят попытка, он дал мне причину, которая была упущена, когда я проверял диалоговое окно сертификата из firefox.

Итак, если сертификат существует в хранилище ключей и его «VALID», эта ошибка исчезнет.

13

combinations vector recursion algorithm c++

задан Jonathan Leffler 10 November 2009 в 16:05

8 ответов

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

5

ответ дан 1 December 2019 в 07:39

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

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

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

3

ответ дан 1 December 2019 в 07:39

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

# Обратите внимание также, что член каждого вектора всегда 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]);
            }
        }
    }
}

1

ответ дан 1 December 2019 в 07:39

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

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

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

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

1

ответ дан 1 December 2019 в 07:39

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

0

ответ дан 1 December 2019 в 07:39

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

-1

ответ дан 1 December 2019 в 07:39

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

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

Сохраните массив итераторов it (размер K) в ваших векторах, начиная с it [i] = v [i] .begin () . Продолжайте увеличивать это [K-1] в цикле. Когда какой-либо итератор достигает end () соответствующего вектора, вы оборачиваете его до begin () и также увеличиваете предыдущий итератор (поэтому, когда он [K-1] ] завершается, вы увеличиваете до [K-2] ). Эти приращения могут «каскадироваться», поэтому вы должны делать их в обратном цикле. Когда он [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 (N ^K - 1) / (N-1) = O (N ^K). Это также означает, что амортизированная стоимость комбинации равна O (1).