Создание списка из пар

Question

У меня есть пары (a1, b1), (a2, b2) ..... (an, bn) Я хочу сгенерировать все 2^n списков. С рекурсией это легко и похоже на нахождение всех перестановок строки, но я хочу сделать это итеративно. Пожалуйста, предложите мне способ сделать это.

Чтобы быть ясным, первое место списка может быть a1 или b1, второе место может быть a2 или b2 .. i-е место может быть ai или bi .... n-е место будет a или bn.

Пример: (a1 a2 .... an) (b1 b2 ..... bn) (b1 a2 ... a) (a1 b2 ..... an) (все 2^n списки)

вот пример рекурсивного кода для n = 3.

#include <iostream> 
#include <string> 
#include <vector> 
#include <utility> 
#include <algorithm> 
using namespace std; 

void compute(int a[][2],int i,vector<int> v) 
{ 
    if(i==3) 
    { 
     for(int j=0;j<v.size();j++) 
      cout<<v[j]<<" "; 
     cout<<endl; 
     return; 
    } 

    for(int j=0;j<=1;j++) 
    { 
     if(j==1) v.pop_back(); 
     v.push_back(a[i][j]); 
     compute(a,i+1,v); 
    } 
} 

int main() 
{ 
    float ans=0; 
    int a[3][2]; 
    for(int i=0;i<=2;i++) 
    { 
     for(int j=0;j<=1;j++) 
     cin>>a[i][j]; 
    } 
    vector <int> v; 
    compute(a,0,v); 
} 

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

Answer 1

Поскольку существует 2^n возможных списков, вы можете обрабатывать переменную итерации как поле бит:

#include <iostream> 
using namespace std; 

typedef unsigned bits; // change to a 64-bit type if needed 

int a[][2] = { { 100, 200 }, { 101, 201 }, { 102, 202 } }; 
int N = sizeof(a)/(2*sizeof(int)); // number of pairs in a 

// 0 <= i < 2^N 
void print_list(bits i) 
{ 
    for(int j=0 ; j<N ; ++j) cout << a[j][(i>>(N-1-j))&1] << ' '; 
    cout << endl; 
} 

int main() 
{ 
    for(bits i=0 ; i < (1<<N) ; ++i) print_list(i); 
    return 0; 
} 

Это выводит

100 101 102 
100 101 202 
100 201 102 
100 201 202 
200 101 102 
200 101 202 
200 201 102 
200 201 202 

Конечно, это не предполагает, что списки не более чем на 31 (или 63), но так как вы хотите, чтобы создать все списки, я не думаю, что они будут больше, чем это.

Answer 2

Попробуйте next_permutation с подходящей функцией компаратора.

Вот пример, который выводит то, что вам требуется (помимо небольших различий форматирования):

#include <iostream> 
#include <string> 
#include <vector> 
#include <utility> 
#include <algorithm> 
using namespace std; 

int main() 
{ 
    vector< pair<string,string> > pvec; 
    pvec.push_back(make_pair(string("a1"), ("b1"))); 
    pvec.push_back(make_pair(string("a2"), ("b2"))); 
    pvec.push_back(make_pair(string("a3"), ("b3"))); 
    vector<string> avec, bvec; 
    for(size_t i = 0; i < pvec.size(); ++i) 
    { 
     avec.push_back(pvec[i].first); 
     bvec.push_back(pvec[i].second); 
    } 
    do 
    { 
     cout << "("; 
     for(size_t i = 0; i < avec.size(); ++i) 
      cout << avec[i] << ", "; 
     cout << ") ("; 
     for(size_t i = 0; i < bvec.size(); ++i) 
      cout << bvec[i] << ", "; 
     cout << ")\n"; 
     next_permutation(bvec.begin(), bvec.end()); 
    } 
    while (next_permutation(avec.begin(), avec.end())); 
    return 0; 
} 

Answer 3

Этот код:

#include <iostream> 
#include <string> 
#include <vector> 
#include <utility> 
#include <cmath> 
using namespace std; 

int main() 
{ 
    vector< pair<string,string> > pvec; 
    pvec.push_back(make_pair(string("a1"), ("b1"))); 
    pvec.push_back(make_pair(string("a2"), ("b2"))); 
    pvec.push_back(make_pair(string("a3"), ("b3"))); 
    vector<bool> cv; 
    for(size_t i = 0; i < pvec.size(); ++i) 
     cv.push_back(false); 
    for(size_t i = 0; i < pow(2, pvec.size()); ++i) 
    { 
     cout << "("; 
     for (size_t k = 0; k < pvec.size(); ++k) 
     { 
      if (cv[ k ]) 
       cout << pvec[ k ].second; 
      else 
       cout << pvec[ k ].first; 
      cout << " "; 
     } 
     bool c = true; 
     for (size_t k = 0; k < pvec.size(); ++k) 
     { 
      bool t = cv[k]; 
      cv[ k ] = (t && !c) || (!t && c); 
      c = t && c; 
     } 
     cout << ")\n"; 
    } 
    return 0; 
} 

будет производить следующий вывод:

(a1 a2 a3) 
(b1 a2 a3) 
(a1 b2 a3) 
(b1 b2 a3) 
(a1 a2 b3) 
(b1 a2 b3) 
(a1 b2 b3) 
(b1 b2 b3)