主页 / coding / 问题 / 79134332
Accepted
haifisch123
Asked: 2024-10-29 00:38:08 +0800 CST

对整数数组使用 next_permutation

  • 772

给定一些数组，我想循环遍历这些数组的所有可能的排列：

这是一个简单的例子：

#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++

2 个回答

  1. Best Answer

    您可以通过间接映射排序数组 { 0, 1, 2 }来实现

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

using namespace std;

int main()
{
    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 ijk[] = { 0, 1, 2 };

    int i = 1;
    do {
        cout << "This is the " << i++ << "-th permutation." << '\n';
        cout << temp[ijk[0]][0] << "  " << temp[ijk[1]][0] << "  " << temp[ijk[2]][0] << '\n';
    } while (next_permutation(ijk, ijk + 3));
}

    输出：

    This is the 1-th permutation.
1  -9  3
This is the 2-th permutation.
1  3  -9
This is the 3-th permutation.
-9  1  3
This is the 4-th permutation.
-9  3  1
This is the 5-th permutation.
3  1  -9
This is the 6-th permutation.
3  -9  1
    • 2

  2. 假设元素是唯一的（就像另一个答案默默假设的那样）您可以计算迭代次数：

    #include <algorithm>
#include <array>
#include <print>

size_t factorial(size_t x)
{
    size_t r = 1;
    while (x > 1)
        r *= x--;
    return r;
}

int main()
try {
    auto A = std::to_array({ 1, 0, 0, 0 });
    auto B = std::to_array({ -9, 0, 0, 0 });
    auto C = std::to_array({ 3, 0, 0, 0 });
    auto temp = std::to_array({ A, B, C });

    const auto n = factorial(temp.size());
    for (size_t i = 1; i <= n; ++i) {
        std::println("This is the {}-th permuation: {::}", i, temp);
        std::next_permutation(temp.begin(), temp.end());
    }

    return 0;
} catch (const std::exception& e) {
    std::print("Exception: {}\n", e.what());
}

    https://godbolt.org/z/oW1Yvsrzh https://godbolt.org/z/MKMMfdf9j

    • 0

相关问题