如何用递归生成给定数组的无重复全排列？

给定数组float val[]={+10, -5, +7, -8};，需要通过递归打印该数组的所有无重复全排列（每个元素仅使用一次）。参考课本中的乘法原理编写了如下代码：

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

typedef struct val_s val_t;
struct val_s
{
    float *choices;
};

void multiplication_principle(val_t *val,float *sol,int n,int pos)
{
    if(pos==n)
    {
        for (int i = 0; i < n; ++i) {
            printf("%3.0f ",sol[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < n; ++i) {
        sol[pos]=val[pos].choices[i];
        multiplication_principle(val,sol,n,pos+1);
    }

}
int main() {
    val_t *v;
    float *sol;
    float val[]={+10, -5, +7, -8};
    int n=4;
    v=malloc( n*sizeof(val_t));
    if(val==NULL)
    {
        exit(1);
    }
    for (int i = 0; i < n ; ++i) {
        v[i].choices=malloc(n*sizeof (float ));
        if(v[i].choices==NULL)
        {
            exit(1);
        }
        for (int j = 0; j < n; ++j) {
            v[i].choices[j]=val[j];
        }
    }
    sol=malloc(n* sizeof(float));
    if(sol==NULL)
    {
        exit(1);
    }
    multiplication_principle(v,sol,n,0);

    return 0;
}

运行后生成大量重复排列，示例如下：

10  10  10  -5
 10  10  10   7
 10  10  10  -8
...（省略部分结果）

需要修改代码，仅输出每个元素仅使用一次的全排列，例如：

10  -5   7  -8
-5  10   7  -8
7  -5   10  -8
...

修改方案 #

原代码的问题在于每一位都从完整数组中选取元素，没有限制元素的重复使用。要实现无重复全排列，核心是记录已使用的元素，通过回溯法避免重复选取。

可以简化原有结构体设计，直接使用原数组，新增一个used数组标记元素是否被使用。修改后的代码如下：

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

// 递归生成无重复全排列
void permute(float *arr, float *sol, int *used, int n, int pos) {
    if (pos == n) {
        // 打印当前排列
        for (int i = 0; i < n; ++i) {
            printf("%3.0f ", sol[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            // 标记当前元素已使用
            used[i] = 1;
            sol[pos] = arr[i];
            // 递归处理下一位
            permute(arr, sol, used, n, pos + 1);
            // 回溯：取消标记，允许后续分支使用该元素
            used[i] = 0;
        }
    }
}

int main() {
    float val[] = {+10, -5, +7, -8};
    int n = 4;
    float *sol = malloc(n * sizeof(float));
    int *used = calloc(n, sizeof(int)); // 初始化为0，0表示未使用

    if (!sol || !used) {
        exit(1);
    }

    permute(val, sol, used, n, 0);

    // 释放内存
    free(sol);
    free(used);
    return 0;
}

关键说明 #

• used数组：长度与原数组一致，used[i]为1表示原数组第i个元素已被选入当前排列，0表示未使用。
• 回溯逻辑：递归调用后将used[i]重置为0，保证同一元素能在其他排列分支中被重新选取。
• 简化结构：去掉了冗余的val_t结构体，直接操作原数组，代码更简洁高效。

运行修改后的代码，将输出所有元素仅出现一次的全排列，符合需求。

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