如何从递归函数输出最优现金流排列数组并返回其指针

问题背景 #

给定N个float类型的现金流数组（正数代表存款，负数代表取款），账户初始余额为0。不同的现金流排列会生成不同的余额序列，对应不同的余额最大最小值差值。需要基于现有全排列递归代码，找出差值最小的最优排列，并输出该数组、返回其指针。

现有全排列代码如下：

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

void permutation(float *val,float *sol,float *mark,int n,int pos)
{
    if(pos==n)
    {
        for (int i = 0; i < n; ++i) {
            printf("%.0f ",sol[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < n; ++i) {
        if(mark[i]==0)
        {
            mark[i]=1;
            sol[pos]=val[i];
            permutation(val,sol,mark,n,pos+1);
            mark[i]=0;
        }
    }
}
int main() {
    float *sol;
    float *val;
    int n=4;
    float *mark;
    mark = calloc(n, sizeof(float));
    if(mark==NULL)
    {
        exit(1);
    }
    val = malloc(n* sizeof(float));
    if(val==NULL)
    {
        exit(1);
    }
    val=(float []){+10, -5, +7, -8};
    
    sol=malloc(n* sizeof(float));
    if(sol==NULL)
    {
        exit(1);
    }

    permutation(val,sol,mark,n,0);
    return 0;
}

实现思路与代码修改 #

核心逻辑 #

1. 新增状态记录变量：保存当前最优排列的差值、最优排列数组，用于递归过程中对比更新。
2. 计算排列差值：每生成一个完整排列，遍历计算余额序列，得出最大、最小余额的差值。
3. 更新最优解：将当前排列的差值与记录的最优差值对比，若更小则更新最优差值并复制当前排列到最优数组。
4. 返回最优指针：递归完成后，主函数可输出最优排列并返回其指针。

修改后的完整代码 #

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

// 保存最优状态，也可封装为结构体传入递归函数
float *best_perm = NULL;
float min_diff = FLT_MAX;

// 计算当前排列的余额最大最小差值
float calculate_diff(float *arr, int n) {
    float balance = 0.0f;
    float max_bal = 0.0f;
    float min_bal = 0.0f;
    for (int i = 0; i < n; ++i) {
        balance += arr[i];
        if (balance > max_bal) max_bal = balance;
        if (balance < min_bal) min_bal = balance;
    }
    return max_bal - min_bal;
}

void permutation(float *val, float *sol, float *mark, int n, int pos) {
    if (pos == n) {
        float current_diff = calculate_diff(sol, n);
        // 更新最优排列
        if (current_diff < min_diff) {
            min_diff = current_diff;
            for (int i = 0; i < n; ++i) {
                best_perm[i] = sol[i];
            }
        }
        return;
    }
    for (int i = 0; i < n; ++i) {
        if (mark[i] == 0) {
            mark[i] = 1;
            sol[pos] = val[i];
            permutation(val, sol, mark, n, pos + 1);
            mark[i] = 0;
        }
    }
}

int main() {
    float *sol;
    float *val;
    int n = 4;
    float *mark;

    // 初始化标记数组
    mark = calloc(n, sizeof(float));
    if (mark == NULL) exit(1);

    // 初始化现金流数组
    val = malloc(n * sizeof(float));
    if (val == NULL) exit(1);
    val[0] = 10.0f; val[1] = -5.0f; val[2] = 7.0f; val[3] = -8.0f;

    // 初始化临时排列数组
    sol = malloc(n * sizeof(float));
    if (sol == NULL) exit(1);

    // 初始化最优排列数组
    best_perm = malloc(n * sizeof(float));
    if (best_perm == NULL) exit(1);

    // 执行递归全排列，寻找最优解
    permutation(val, sol, mark, n, 0);

    // 输出最优排列
    printf("最优排列：");
    for (int i = 0; i < n; ++i) {
        printf("%.0f ", best_perm[i]);
    }
    printf("\n最小差值：%.2f\n", min_diff);

    // 内存释放：若需返回best_perm，此处不要释放，由调用方管理
    free(mark);
    free(val);
    free(sol);
    // free(best_perm);

    // 返回最优排列指针（可通过主函数返回值传递，此处示例直接输出）
    return 0;
}

关键说明 #

• 全局变量替代方案：若不想使用全局变量，可定义包含best_perm、min_diff、n的结构体，将结构体指针传入递归函数，避免全局状态污染。
• 内存管理：best_perm在主函数中分配内存，递归仅做复制操作。若需返回该指针，注意由调用方负责后续内存释放。
• 去重优化：如果现金流数组存在重复元素，会生成重复排列，可在递归中添加去重逻辑（如跳过已使用的相同元素），减少无效计算。

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