C语言生成全排列列表的代码错误排查及逻辑疑问

我编写了一段C语言代码，意图生成数组的所有全排列并存储到列表中，但运行后仅重复输出两种排列（321和123）。调整重置交换的位置后，要么重复输出初始排列123六次，要么出现数组越界或其他重复情况。原代码及运行结果如下：

#include <stdio.h>
#include <stdlib.h>

int maxI(int n)
{
    int result = 1;
    for (int i = 1; i <= n; i++)
    {
        result *= i;
    }
    return result;
}

void swap(int *x, int *y)
{
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

int **pMut(int *arr, int size, int max)
{
    int **results = (int **)malloc(sizeof(int *) * max);

    // pointer index, outer loop with reset, inner loop with swaps
    int index, x, y;

    for (index = 0; index < max; index++)
    {
        results[index] = (int *)malloc(sizeof(int) * size);

        for (x = 0; x < size - 1; x++)
        {
            for (y = 1; y < size; y++)
            {
                swap(&arr[x], &arr[y]);

                for (int z = 0; z < size; z++)
                {
                    results[index][z] = arr[z];
                }
            }
        }
    }

    swap(&arr[x], &arr[y]);

    return results;
}

int main()
{
    int target[] = {1, 2, 3};
    int size = sizeof(target) / sizeof(target[0]);
    int max = maxI(size);
    int **result = pMut(target, size, max);

    for (int index = 0; index < max; index++)
    {
        for (int x = 0; x < size; x++)
        {
            printf("%d", result[index][x]);
        }
        printf("\n");
    }

    for (int i = 0; i < max; i++)
    {
        free(result[i]);
    }

    free(result);

    return 0;
}

运行结果：

321
123
321
123
321
123

错误分析 #

• 核心逻辑错误：原pMut函数的嵌套循环逻辑完全不符合全排列生成规则。全排列需要通过回溯法（固定当前位置，递归生成后续元素的排列，完成后交换回原状态）实现，而原代码只是反复交换数组的前两个元素，导致数组在123和321之间来回切换，最终每个results[index]被多次覆盖后只保留最后一次交换的结果，外层循环重复6次就出现交替重复输出。
• 无效的末尾交换：函数末尾的swap(&arr[x], &arr[y])属于未定义行为，循环结束后x和y的值已超出数组索引范围，访问该位置会导致数组越界。
• 结果覆盖问题：每个index循环内，内层嵌套交换会多次将当前数组状态赋值给results[index]，最终results[index]只保留最后一次交换后的数组，而非生成新排列。

修正后的代码 #

采用回溯递归的方式实现全排列生成，代码如下：

#include <stdio.h>
#include <stdlib.h>

// 计算阶乘，获取全排列总数
int maxI(int n)
{
    int result = 1;
    for (int i = 1; i <= n; i++)
    {
        result *= i;
    }
    return result;
}

// 交换数组元素
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

// 回溯生成全排列的核心函数
void backtrack(int *arr, int size, int start, int **results, int *count)
{
    // 当start到达数组末尾时，记录当前排列
    if (start == size)
    {
        results[*count] = (int *)malloc(sizeof(int) * size);
        for (int i = 0; i < size; i++)
        {
            results[*count][i] = arr[i];
        }
        (*count)++;
        return;
    }

    // 固定start位置，依次交换后续元素生成不同排列
    for (int i = start; i < size; i++)
    {
        swap(&arr[start], &arr[i]);
        backtrack(arr, size, start + 1, results, count);
        swap(&arr[start], &arr[i]); // 回溯，恢复原数组状态
    }
}

// 生成全排列的入口函数
int **pMut(int *arr, int size, int max)
{
    int **results = (int **)malloc(sizeof(int *) * max);
    int count = 0;
    backtrack(arr, size, 0, results, &count);
    return results;
}

int main()
{
    int target[] = {1, 2, 3};
    int size = sizeof(target) / sizeof(target[0]);
    int max = maxI(size);
    int **result = pMut(target, size, max);

    // 输出所有排列
    for (int index = 0; index < max; index++)
    {
        for (int x = 0; x < size; x++)
        {
            printf("%d", result[index][x]);
        }
        printf("\n");
    }

    // 释放内存
    for (int i = 0; i < max; i++)
    {
        free(result[i]);
    }
    free(result);

    return 0;
}

运行结果：

123
132
213
231
321
312

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