c++ - 在C++中查找置换和组合

Question

我想在C++中找到一系列动态长度。假设我有两组数字:arr1[3] = {1, 3, 8}和arr2[4] = {2, 9}，那么预期的输出是:

'1, 2',
'1, 9',
'3, 2',
'3, 9',
'8, 2',
'8, 9'.

但是，如果现在有3个组: arr1[3] = {1, 3, 8}， arr2[2] = {2, 9}和 arr3[5] = {1, 3, 9}，则输出应为:

'1, 2, 1',
'1, 2, 3',
'1, 2, 9',
'1, 9, 1',
'1, 9, 3',
'1, 9, 9',
'3, 2, 1',
'3, 2, 3',
'3, 2, 9',
'3, 9, 1',
'3, 9, 3',
'3, 9, 9',

等等...

因此，将有3 x 2 x 3 = 18个结果。使用各自的for循环次数，我得到了2组和3组的结果。

参见以下代码分为2组:

for(int i=1;i<=5;i++) { 
   for (int j=1;j<=5;j++) { 
       cout << i << "," << j << "," << endl; 
   } 
}

但是然后我必须对组号的不同值使用不同的代码，并且必须使用switch语句或if-else语句来选择那部分代码。

这将是很大的帮助。提前致谢!

Answer 1

我使用 vector 而不是数组，因为它们更容易处理。

技巧是按字典顺序枚举数组中的位置，然后显示这些位置的值:

#include <vector>
#include <iostream>

using std::vector;

void permutate(vector<vector<int>> values)
{
    // the positions in each vector
    vector<size_t> pos(values.size());

    do
    {
        // display one of each array at current position
        for(size_t i = 0; i < values.size(); ++i)
        {
            std::cout << values[i][pos[i]] << ", ";
        }
        std::cout << std::endl;

        // increment the last array's display position
        size_t p = 0;
        pos[p]++;

        // while we get to the end of current array, return to 0 and carry to next position
        while(pos[p] == values[p].size())
        {
            pos[p] = 0;
            p++;
            pos[p]++;

            // return when the last array's position get to its size
            if (p == values.size())
            {
                return;
            }
        }
    }
    while(true);

}

int main()
{
    vector<int> arr1 = {1, 3, 8};
    vector<int> arr2 = {2, 9};
    vector<int> arr3 = {1, 3, 9};

    vector<vector<int>> allThree = {arr1, arr2, arr3};

    permutate(allThree);
}

接下来，一个好的练习是对其进行模板化，以便您接受 std::vector<std::vector<T>>