1

(a1,b1) 、 (a2, b2) ..... (an,bn) のペアがあります。2^n 個のリストをすべて生成したいと考えています。再帰を使用すると、これは簡単で、文字列のすべての順列を見つけるようなものですが、繰り返し実行したいと考えています。これを行う方法を教えてください。

明確にするために、リストの 1 位は a1 または b1、2 位は 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

このコード:

#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 に答える
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 に答える