1

我有对 (a1,b1) , (a2, b2) ..... (an,bn) 我想生成所有 2^n 列表。使用递归这很容易，就像找到字符串的所有排列一样，但是我想迭代地做。请建议我一种方法来做到这一点。

需要明确的是，列表的第一个位置可以是 a1 或 b1，第二个位置可以是 a2 或 b2 .. 第 i 个位置可以是 ai 或 bi....第 n 个位置是 an 或 bn。

示例： (a1 a2 .... an) (b1 b2 ...bn) (b1 a2 ...an) (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，如果我通过引用传递，代码将不起作用

4

3 回答 3

5

由于有 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），但由于您想生成所有列表，我不认为它们会比这更长。

于 2013-09-11T00:29:55.893 回答
0

使用合适的比较器函数尝试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;
}
于 2013-09-10T17:41:39.010 回答
0

这段代码：

#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 )
于 2013-09-10T19:27:09.433 回答