在整数数组上使用 next_permutation

问题描述 投票:0回答:1

给定一些数组,我想循环这些数组的每个可能的排列:

这是一个最小的例子:

#include <array>
#include <iostream>
//#include <random>
#include <algorithm>

using namespace std;

int main() {
    // Change the first number of the arrays to get a different number of permutations
    // (this is not wanted)
    array<int, 4> A = { 1,0,0,0 };
    array<int, 4> B = { -9,0,0,0 };
    array<int, 4> C = { 3,0,0,0 };
    array<int, 4> temp[3] = { A, B, C };

    int i = 1;
    do {
        cout << "This is the " << i++ << "-th permutation." << endl;
    } while (next_permutation(temp, temp + 3));
    // (it should yield 3! = 6 permutations but only yields 4)

    return 0;
}

然而,循环排列的数量似乎取决于数组的起始值(这不是我希望在项目中使用的功能)。

这是因为 next_permutation 按字典顺序对元素进行排序。

如何使用此函数来获取给定数组的所有排列? 或者我必须使用完全不同的方法吗?

我也知道这个答案,但我想避免事先对数组进行排序,因为我计划使用大量数组。

谢谢!

c++ arrays permutation
1个回答
0
投票

你就快到了,正如迈尔斯所说,你需要先对数组进行排序。 这是一个更新的示例(不使用

using namespace
)并直接将您的值初始化为二维数组

#include <array>
#include <iostream>
#include <algorithm>

std::ostream& operator<<(std::ostream& os, const std::array<int,4>& values)
{
    os << "[" << values[0] << ", " << values[1] << ", " << values[2] << ", " << values[3] << "]";
    return os;
};

int main() 
{
    // Change the first number of the arrays to get a different number of permutations
    // (this is not wanted)
    std::array<std::array<int, 4>,3> values 
    {{
        { 1,0,0,0 },
        { -9,0,0,0 },
        { 3,0,0,0 }
     }};

    std::sort(values.begin(),values.end());
    
    int i = 1;
    do
    {
        std::cout << "\n This is the " << i++ << "-th permutation.\n";
        for(const auto& arr : values)
        {
            std::cout << arr << "\n";
        }

    } while (std::next_permutation(values.begin(),values.end()));
    

    return 0;
}
© www.soinside.com 2019 - 2024. All rights reserved.