Generating list out of pairs

Question

I have pairs (a1,b1) , (a2, b2) ..... (an,bn) I want to generate all the 2^n lists. With recursion this is easy and is like finding all permutations of string however I want to do it iteratively. Please suggest me a way to do this.

To be clear the first place of list can be a1 or b1 the second place can be a2 or b2 .. the ith place can be ai or bi....the nth place will be an or bn.

Example: (a1 a2 .... an) (b1 b2 ..... bn) (b1 a2 ...an) (a1 b2 .....an) (all 2^n lists)

here is a sample recursive code for 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);
}

I want to use iterative code to improve performance both in terms of speed and more importantly on space because now I have to pass by value so the new vector v is being created every time and the code will not work if I pass by reference

Answer 1

Since there are 2^n possible lists, you can treat the iteration variable as a bit field:

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

This outputs

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

Granted, this assumes the lists are no longer than 31 (or 63) but since you want to generate all lists, I don't imagine they will be longer than this.

Answer 2

This code:

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

Will produce the following output:

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

Answer 3

Try next_permutation with a suitable comparator function.

Here is an example that outputs what you require (besides small formatting differences):

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