如何将Heap's Algorithm生成的全排列结果保存为列表？

你遇到的核心问题是原代码仅打印排列，未收集结果；修改返回类型时因代码路径未全覆盖返回值导致报错。以下是两种可行的修改方案：

方案一：通过参数传递结果列表（高效推荐） #

这种方式利用引用类型的特性，在递归过程中直接向结果列表添加排列，避免频繁创建和合并列表，性能更优。

修改后的代码：

// 递归生成排列，结果存入传入的result列表
static void heapPermutation(int[] a, int size, int n, List<List<int>> result)
{
    // 当size为1时，当前数组即为一个有效排列，复制后存入结果
    if (size == 1)
    {
        result.Add(a.Take(n).ToList());
        return;
    }

    for (int i = 0; i < size; i++)
    {
        heapPermutation(a, size - 1, n, result);

        // 根据size奇偶性执行交换
        if (size % 2 == 1)
        {
            (a[0], a[size - 1]) = (a[size - 1], a[0]);
        }
        else
        {
            (a[i], a[size - 1]) = (a[size - 1], a[i]);
        }
    }
}

// 调用示例
static void Main()
{
    int[] arr = { 1, 2, 3 };
    List<List<int>> allPermutations = new List<List<int>>();
    heapPermutation(arr, arr.Length, arr.Length, allPermutations);

    // 输出验证
    foreach (var perm in allPermutations)
    {
        Console.WriteLine(string.Join(" ", perm));
    }
}

关键说明： #

• 必须复制当前数组元素存入结果：数组是引用类型，直接添加a会导致后续交换修改已存入的排列，所以用a.Take(n).ToList()创建新列表。
• 方法保持void返回类型，通过参数传递结果，避免返回值相关的编译错误。

方案二：让递归方法直接返回结果列表 #

如果希望方法直接返回排列列表，需确保所有代码路径都返回值，递归时合并子问题的结果：

修改后的代码：

// 递归生成并返回所有排列的列表
static List<List<int>> heapPermutation(int[] a, int size, int n)
{
    List<List<int>> result = new List<List<int>>();

    if (size == 1)
    {
        result.Add(a.Take(n).ToList());
        return result;
    }

    for (int i = 0; i < size; i++)
    {
        // 合并子递归返回的排列
        result.AddRange(heapPermutation(a, size - 1, n));

        // 根据size奇偶性执行交换
        if (size % 2 == 1)
        {
            (a[0], a[size - 1]) = (a[size - 1], a[0]);
        }
        else
        {
            (a[i], a[size - 1]) = (a[size - 1], a[i]);
        }
    }

    return result;
}

// 调用示例
static void Main()
{
    int[] arr = { 1, 2, 3 };
    List<List<int>> allPermutations = heapPermutation(arr, arr.Length, arr.Length);

    // 输出验证
    foreach (var perm in allPermutations)
    {
        Console.WriteLine(string.Join(" ", perm));
    }
}

关键说明： #

• 所有分支都有return语句：size==1时返回包含当前排列的列表，循环结束后返回合并后的总结果，解决了“并非所有代码路径都返回值”的错误。
• 每次递归都会创建新列表并合并，适合小规模数组，大规模数据推荐方案一。

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