c++ - 在 C++ 中生成排列的递归问题

Question

我在 C++ 中有两个 n，我想以这种方式生成这些 vector 中数字的排列，对于第一个 vector 的每个排列，我拥有所有其他 vector 的所有排列。假设我有两个数字为 2 9 的 vector ，另一个 vector 为 5 6。那么我的结果应该是...

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

意味着我得到的排列总数将是总 perms =(第一个 vector 的排列数乘以第二个 vector 的排列数乘以第三个 vector 的排列数，依此类推)。

我已经写了下面的代码，我被递归堆栈打动了......它实际上打印了 6 次，因为 2 个 vector 的大小分别为 2。

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

交换两个 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;
}

我的主要功能。

请给我一些提示或针对一般情况解决这个问题，因为上面的代码打印了 6 个原本应该是 4 次的排列。

谢谢

Answer 1

考虑到这不是作业，您可以简单地使用 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;
}

这适用于两个 vector ...我相信您可以进一步概括它。