Heap排列生成算法实现异常：生成重复排列结果

问题现象 #

实现Heap's算法生成列表全排列时，生成的排列总数符合n!，但部分排列缺失，空缺被已有排列的副本填充。

3个元素的输出（重复项已标记）：

0, 1, 2,
1, 0, 2,
2, 1, 0, f
1, 2, 0, f
2, 1, 0, s
1, 2, 0, s

4个元素的输出（重复项已标记）：

0, 1, 2, 3,
1, 0, 2, 3,
2, 1, 0, 3, f
1, 2, 0, 3, f
2, 1, 0, 3, s
1, 2, 0, 3, s
3, 1, 2, 0,
1, 3, 2, 0, f
2, 1, 3, 0,
1, 2, 3, 0, f
0, 1, 3, 2,
1, 0, 3, 2,
1, 3, 2, 0, s
0, 3, 2, 1,
2, 3, 1, 0, f
0, 3, 1, 2, f
3, 2, 1, 0, f
1, 2, 3, 0, s
2, 3, 1, 0, s
0, 3, 1, 2, s
3, 2, 1, 0, s
1, 2, 3, 0, t
2, 3, 1, 0, t
0, 3, 1, 2, t

原实现代码 #

vector<vector<int>> permutations;

void GenerateAllPermutations(vector<int> v, int size)
{
    // if size becomes 1 then adds on the obtained permutation
    if (size == 1) {
        permutations.push_back(v);
        return;
    }

    for (int i = 0; i < size; i++) {
        GenerateAllPermutations(v, size - 1);

        // if size is odd, swap first and last element
        if (size % 2 == 1)
        {
            iter_swap(v.begin(), v.begin() + v[size - 1]);
        }
        // If size is even, swap ith and last element
        else
        {
            iter_swap(v.begin() + i, v.begin() + v[size - 1]);
        }
    }
}

int main()
{
    vector<int> v = { 0, 1, 2, 3 };
    GenerateAllPermutations(v, v.size());
    // prints all the generated permutations
    for (int i = 0; i < permutations.size(); i++)
    {
        for (int x = 0; x < permutations[i].size(); x++)
        {
            cout << permutations[i][x] << ", ";
        }
        cout << endl;
    }
}

问题原因 #

核心错误：交换元素时误用了v[size-1]作为索引——这是取当前数组最后一个位置的元素值，而Heap's算法要求的是和**当前处理范围的最后一个位置（固定索引为size-1）**交换元素。

当数组元素发生位置变化后，v[size-1]会变成非预期的数值，导致交换位置完全错误，最终生成大量重复排列，同时丢失正确的排列组合。

修正后的代码 #

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> permutations;

void GenerateAllPermutations(vector<int> v, int size)
{
    if (size == 1) {
        permutations.push_back(v);
        return;
    }

    for (int i = 0; i < size; i++) {
        GenerateAllPermutations(v, size - 1);

        // 奇数size：交换首元素和当前范围的最后一个元素（索引size-1）
        if (size % 2 == 1)
        {
            iter_swap(v.begin(), v.begin() + size - 1);
        }
        // 偶数size：交换第i个元素和当前范围的最后一个元素（索引size-1）
        else
        {
            iter_swap(v.begin() + i, v.begin() + size - 1);
        }
    }
}

int main()
{
    vector<int> v = { 0, 1, 2, 3 };
    GenerateAllPermutations(v, v.size());
    
    for (const auto& perm : permutations)
    {
        for (size_t idx = 0; idx < perm.size(); idx++)
        {
            cout << perm[idx];
            if (idx != perm.size() - 1) cout << ", ";
        }
        cout << endl;
    }
    
    return 0;
}

补充说明 #

1. 修正了交换逻辑，将v[size-1]替换为size-1，确保交换的是当前处理范围的最后一个位置，而非该位置的元素值对应的索引。
2. 保留原代码中vector<int> v的传值方式，每次递归调用复制当前数组状态，避免递归修改影响上层调用的数组。
3. 优化了打印逻辑，避免最后多输出一个逗号。

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