如何在不耗尽内存的情况下找到固定和与长度的最小标准差整数组合？

我需要遍历所有给定总和与长度的整数组合，找到标准差最小的组合。比如总和为4、长度为2时，所有可能组合是[4,0], [3,1], [2,2], [1,3], [0,4]。我用递归方法distributeFacilities实现了遍历，其中remainingFacilities是剩余总和，numberOfTransformers是组合长度，allPossibleFacilityCombinations用来存所有组合。但当输入totalNumberOfFacilities=213、numberOfTransformers=6时，组合总数高达3917788308，直接存储所有组合会内存耗尽，请问怎么在不耗尽内存的情况下找到最优组合？

附上的实现代码：

private ArrayList<ArrayList<Integer>> allPossibleFacilityCombinations = new ArrayList<>();;

private void distributeFacilities(int remainingFacilities, int numberOfTransformers,
        ArrayList<Integer> facilitiesPerTransformer, int currentIndex) {
    if (currentIndex == numberOfTransformers) {
        if (remainingFacilities == 0) {
            // Create a new ArrayList based on facilitiesPerTransformer
            ArrayList<Integer> copy = new ArrayList<>(facilitiesPerTransformer);
            allPossibleFacilityCombinations.add(copy);
        }
        return;
    }

    for (int i = 0; i <= remainingFacilities; i++) {
        facilitiesPerTransformer.add(i);
        distributeFacilities(remainingFacilities - i, numberOfTransformers, facilitiesPerTransformer,
                currentIndex + 1);
        facilitiesPerTransformer.remove(facilitiesPerTransformer.size() - 1);
    }
}

public static void main(String[] args) {
    //some code where I get totalNumberOfFacilities and numberOfTransformers

    ArrayList<Integer> facilitiesPerTransformer = new ArrayList<>();
    mainInstance.distributeFacilities(remainingFacilities, numberOfTransformers, facilitiesPerTransformer, 0);
}

根本不需要遍历所有组合，数学上可以直接推导出差标准差最小的最优组合——数值尽可能平均分配的整数组合。

核心原理 #

标准差衡量数据的离散程度，数据越接近平均值，离散程度越小，标准差也就越小。对于总和S、长度n的整数组合，最优解的元素只能是floor(S/n)或ceil(S/n)，因为这两个值是最接近平均值的整数。

具体生成方法 #

1. 计算整数商：quotient = S / n（即平均值向下取整）
2. 计算余数：remainder = S % n（总和除以长度后剩下的部分）
3. 最终组合包含remainder个quotient + 1，以及n - remainder个quotient

举两个例子验证：

• 总和4、长度2：quotient=2，remainder=0，组合为[2,2]，确实是标准差最小的
• 总和213、长度6：213/6=35，余数3，组合为[36,36,36,35,35,35]（顺序不影响标准差）

替代代码实现 #

直接生成最优组合，无需遍历任何其他组合，彻底避免内存问题：

public ArrayList<Integer> getOptimalCombination(int totalFacilities, int transformerCount) {
    ArrayList<Integer> optimalCombination = new ArrayList<>();
    int base = totalFacilities / transformerCount;
    int extraCount = totalFacilities % transformerCount;

    // 添加需要+1的元素
    for (int i = 0; i < extraCount; i++) {
        optimalCombination.add(base + 1);
    }
    // 添加剩余的基础值元素
    for (int i = 0; i < transformerCount - extraCount; i++) {
        optimalCombination.add(base);
    }
    return optimalCombination;
}

为什么这个方案可行 #

所有其他组合的元素与平均值的偏差都会大于或等于这个平均分配组合的偏差，因此它的标准差必然是最小的。直接生成该组合跳过了遍历海量组合的过程，从根源解决了内存耗尽的问题，同时时间复杂度仅为O(n)，效率极高。

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