2

私はc++に2つのnを持っており、最初のベクトルの順列ごとに、他のすべてのベクトルのすべての順列を持つように、これらのベクトルの数値の順列を生成したいと考えています。番号29の2つのベクトルがあり、もう1つのベクトルは5 6になるとすると、結果は次のようになります。

  1. 2 9 5 6
  2. 2 9 6 5
  3. 9 2 5 6
  4. 9 2 6 5

つまり、取得した順列の総数は、合計perms =（1番目のベクトルの順列の数×2番目のベクトルの順列の数×3番目のベクトルの順列の数など）になります。

私は以下のコードを書きました、そして私は再帰スタックに打たれました...それはそれぞれがそれぞれ2のサイズを持つ2つのベクトルの場合に実際に6回印刷しています。

mySwap(int *x, int *y){
int temp;
temp = *x;
    *x = *y;
*y = temp;
}

2つのint要素を交換します

void myPerm(vector<vector<int>> myItems, int start, int end,int     vectorIndex){
int j;
if(start == end){
    for(int k = vectorIndex +1; k < items.size(); ++k){
        myPerm(myItems, 0, myItems[k].size()-1,k);
    }
    for(int z = 0; z < myItems.size(); ++z){
        for(int l = 0; l < myItems[z].size(); ++z){
            std::cout << myItems[z][l];
        }
    }
}
else{
    for(int j = start; j <= end; j++){
        mySwap(&myItems[vectorIndex][start],&myItems[vectorIndex][j]);
        myPerm(myItems,start + 1, end,vectorIndex);
        mySwap(&myItems[vectorIndex][start],&myItems[vectorIndex][j]);

    }   

}
}

順列を再帰的に生成する上記のコード...

int main(){
vector<vector<int>> myItems;
int k = 0;
for(int i =0; i < 2; ++i){
    myItems.push_back(vector<int>);
}
for(int j =0; j < 2; ++j){
    myItems[i].push_back(k++);
}

myPerm(items,0,items[0].size()-1,0);
return;
}

私の主な機能。

上記のコードは元々4倍であるはずの6つの順列を出力するため、一般的なケースについてヒントを与えるか、これを解決してください。

ありがとう

4

3 に答える 3

0

これが宿題ではないことを考えると、あなたはあなたが持っているものの代わりに単にstlアルゴリズムnext_permutationを使うことができ ます。

これは、サンプル入力のコードです。 

int main()
{

    std::vector<int> v1 , v2 , v3;
    v1.push_back( 2 );
    v1.push_back( 9 );
    v2.push_back( 5 );
    v2.push_back( 6 );

    std::sort( v1.begin() , v1.end() );
    std::sort( v2.begin() , v2.end() );

    do 
    {   
        v3 = v2;

        do 
        {
            std::for_each( v1.begin() , v1.end() , [](int x) { std::cout << x << " ";} );
            std::for_each( v3.begin() , v3.end() , [](int x) { std::cout << x << " ";} );
            std::cout << std::endl;
        } 
        while ( std::next_permutation(v3.begin() , v3.end() ) );
    } 
    while ( std::next_permutation(v1.begin() , v1.end() ) );

    return 0;
}

これは2つのベクトルに対してそれを行います...私はあなたがそれをさらに一般化できると確信しています。

于 2011-12-24T18:08:07.620 に答える
0

特にSTL関数next_permutationのすべてのアイデアに感謝します。早くはわかりません。

欲しいコードを正しく書くことができました...

これが私のコードです

void perm(std::vector<std::vector <int>> &items, int level){
if(level == 0){
for (int i = 0; i < items.size(); i++)
  for (int j = 0; j < items[i].size(); j++)
      std::cout << items[i][j];
std::cout<<std::endl;


    while(next_permutation(items[level].begin(), items[level].end())){
        for (int i = 0; i < items.size(); i++)
          for (int j = 0; j < items[i].size(); j++)
              std::cout << items[i][j];
        std::cout<<std::endl;
    }
}
else{

    if(level > 0)
    perm(items,level-1);
    while(next_permutation(items[level].begin(), items[level].end())){
        if(level > 0)
        perm(items,level-1);
    }

}

}

于 2011-12-24T21:45:47.947 に答える
-1

この問題では、を使用して再帰を完全に省略できますnext_permutation。間違いなくよりエレガントなテストされていないコードを次に示します。

void myPerm(std::vector<std::vector<int>>& myItems)
{
    for (int i = 0; i < myItems.size(); i++)
        std::sort(myItems[i].begin(), myItems[i].end());

    int level;

    do
    {
        printAll(myItems);

        level = myItems.size() - 1;

        while (!next_permutation(myItems[level].begin(), myItems[level].end()))
            level--;
    }
    while (level >= 0);
}

良い点next_permutationは、指定されたセットを「ラップアラウンド」するときにfalseを返すため、セットがソートされ、次の順列の準備ができていることです。

于 2011-12-24T18:48:16.730 に答える