Como criar combinações de vários vetores sem loops de codificação de disco rígidos em C ++?

StackOverflow https://stackoverflow.com/questions/1700079

Pergunta

Eu tenho vários dados que se parece com isso: 

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.

O que eu quero fazer é criar todas as combinações de elementos em Vector1 através de fora VectorK. Assim, no final, esperamos obter esta saída (usando 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

O problema que estou tendo agora é que o seguinte código de mina faz que por codificar os loops. Desde número de vetores podem ser variadas, precisamos de uma maneira flexível para obter o mesmo resultado. Existe alguma?

Este código da mina só pode lidar com até 3 Vetores (codificado): 

#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;
}
Foi útil?

Solução

Isto irá fazer o truque: 

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

Chamada com: 

printAll(allVecs, 0, "");

Outras dicas

Você pode implementar isso como um conta-quilómetros, o que leva à seguinte (obras para vetores de tamanhos diferentes):

Digamos que você tenha vetores K em uma matriz v: v[0], v[1], ... v[K-1]

Mantenha um conjunto de iteradores it (tamanho K) em seus vetores, começando com it[i] = v[i].begin(). Mantenha incrementando it[K-1] em um loop. Quando qualquer iterador atinge o end() do vector correspondente, você envolvê-la em torno de begin() e incrementar o iterador anterior também (assim quando it[K-1] envolve, você it[K-2] incremento). Estes incrementos podem "cascata" de modo que você deve fazê-las em um loop para trás. Quando it[0] envolve, você está feito (assim sua condição de loop poderia ser algo como while (it[0] != v[0].end())

Colocando tudo isso junto, o loop que faz o trabalho (depois de configurar os iteradores) deve ser algo como: 

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

Se você estiver interessado em complexidade, o número de iteradoras incrementos que são executadas é fácil de calcular. Para simplificar aqui eu vou assumir cada vetor é o mesmo N. comprimento O número total de combinações é N K . A última iteração é incrementado a cada vez, de modo que é N K , e de volta através dos iterators esta contagem é dividido por N de cada vez em movimento, por isso temos N K + N K-1 + ... N 1 ; esta soma é igual a N (N K - 1) / (N-1) = O (N K ). Isto também significa que o custo amortizado por combinação é O (1).

De qualquer forma, em suma, tratá-lo como um conta-quilómetros girando suas rodas de dígitos.

A C ++ 0x solução. Desde que, claro, seus apoios compilou (atualmente GCC 4.5 e VS2010, eu acho).

Os seguintes compila e funciona com GCC 4.5, usando interruptor -std=c++0x. O uso de modelos variádicos torna possível combinar número arbitrário de recipientes. Tenho certeza que você pode vir até com uma solução mais idiomática. 

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

A dificuldade básica com recursão aqui é que você precisa manter o controle de toda a lista de índices (ou construir outra coisa a corda de forma incremental, como outro pergunta pontos fora).

Uma maneira conveniente para lidar com esse problema sem a construção de objetos adicionais dentro dos laços é entregar a sua função recursiva um vetor de índices, do mesmo comprimento que o vetor de vetores: 

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

Combinando três vectores é essencialmente o mesmo que o primeiro combinando dois vectores, e, em seguida, combinando a terceira um com o resultado.

Então, tudo se resume a escrever uma função que pode combinar dois vetores. 

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

E então algo como: 

std::vector< std::string > result = combine(Vec1, Vec2);
result = combine(result, Vec3);

e assim por diante para cada vector que você precisa combinado.

Note que é mais o "caminho C ++" para uso de entrada e de saída iterators I.S.O. passando vetores ao redor, e muito mais eficiente. Na versão acima do vetor é copiado mais e mais ...

Eu simplesmente vetores usados ??para ficar mais perto de seu código original e, esperançosamente, fazer mais sentido para você.

Uma vez que você parece querer cada saída ser o comprimento dos vectores individuais, e você parece saber que cada vector é de 3 elementos de largura a partir

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

usando recursão para uma solução geral parece um pouco exagero aqui.

Você pode usar algo assim: 

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

Eu também estou interessado em construir algum tipo de fácil de enxaguar e repetir combinatória. Estou familiarizado com o tipo de abordagem orientada hodômetro, se quiser, onde você tem índices de pé. Algo ao longo dessas linhas. O ponto é, para construir facilmente as tuplas através de um conjunto arbitrário de vetores não relacionados.

Este não chega a responder à sua pergunta, eu não acho, mas você poderia construir static / projeto combinações de tempo usando uma produção variádica tais como o seguinte, onde T1-3 são tipos arbitrários: 

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

Assumindo que você tem um vector que é algo como isto: 

typedef vector<tuple<T1, T2, T3>> CombosVector;

CombosVector combos;

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

Como eu disse, esta é uma consideração tempo de design. Ele não constrói tuplas em toda uma série tempo de execução de vetores. Esse é o lado de baixo. O lateral-se, no entanto, é que você ganha compreensão tempo de compilação de seus tuples vectored.

Mais uma vez, não é o que você, ou eu mesmo, estão atrás, mas talvez ele ajuda faísca comentários favoráveis.

solução acima PRINTALL irá falhar quando vetores são de não mesmo tamanho.

Fixed essa questão: 

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

A maneira mais simples de abordar esta questão é usar recursão. A função terá um laço nele e vai chamar-se, fundindo-se com a saída da chamada recursiva. Claro, a recursividade pode ser convertido para iteração se você está preocupado com o espaço de pilha, mas pelo menos como ponto de partida, a solução recursiva provavelmente será mais fácil para você.

Use a função next_permutation implementado em std da STL

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top