使用next_permutation获取int数组全排列遇问题的解决方案咨询

我需要遍历若干int类型数组的所有可能排列，写了一段最简示例代码，但实际得到的排列数依赖于数组初始值，无法得到全部3! = 6种排列，只能得到4种。原因是next_permutation按字典序排列元素。我想知道如何用该函数获取全部排列？或者是否必须用其他方法？另外我知道可以预先排序，但计划处理大量数组，希望避免预先排序。

示例代码：

#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的工作机制：它只会生成当前序列之后的字典序排列，直到序列变成降序为止。你的初始数组序列不是字典序最小的状态，所以它没法覆盖所有6种排列，只能生成从当前状态往后的4种。

如果不想预先对数组排序，最稳妥的办法是通过索引排列间接实现，具体思路是：

• 先创建一个索引数组，比如你有3个数组，就用{0,1,2}；
• 对这个索引数组使用next_permutation——因为索引数组初始是严格升序的，所以能生成全部3! = 6种排列；
• 每次拿到一组索引排列，就用索引去原数组里取对应的元素，这样就得到了原数组的一种排列。

修改后的代码如下：

#include <array>
#include <iostream>
#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> arr_list[] = { A, B, C };
    const int arr_count = sizeof(arr_list)/sizeof(arr_list[0]);
    
    // 初始化索引数组
    int indices[] = {0, 1, 2};
    int perm_count = 1;
    do {
        cout << "这是第" << perm_count++ << "种排列：" << endl;
        // 通过索引访问原数组元素
        for (int idx : indices) {
            // 这里示例打印数组第一个元素，可按需修改
            cout << arr_list[idx][0] << " ";
        }
        cout << endl;
    } while (next_permutation(indices, indices + arr_count));

    return 0;
}

这个方法的好处：

• 不用改动原数组的顺序，完全避免了对大量数组排序的开销；
• 索引数组本身是简单的整数数组，排序、生成排列的成本极低；
• 不管原数组的元素是什么样，只要索引数组是升序初始状态，就能生成全部排列。

内容的提问来源于stack exchange，提问作者haifisch123