将穷举增量分布到固定数量的槽中的算法

Question

我有一个正在构建的模拟，我需要一种算法来 distribute/redistribute 一个固定的总浮点值按设定的增量分成 10 个不同的 "slots" 并重复该过程直到所有的排列都被模拟。我知道我必须设置一个界限，因为我正在处理浮点值。

在最简单的情况下，我要分配 10 个槽和 10.0 的总值，最小增量为 1.0，因此我只使用整数。所以我希望能够运行从这一点开始模拟：

| 10 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |

至此：

|  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 | 10 |

中间总和为 10.0 的所有可能的排列。

我知道我可以通过数学运算来计算排列数，但我只是不确定如何设计算法来实现这一点。有什么想法吗？

Answer 1

我不知道你选择的语言是什么，但是 Java 中有一个解决方案。

public static void main(String[] args) {
    slots(4, 0, new int[3]);
}

private static void slots(int sum, int index, int[] array) {
    if (index == array.length - 1) {
        array[index] = sum;
        // Do something with the array here.
    } else {
        for (int i = 0; i <= sum; i++) {
            array[index] = i;
            slots(sum - i, index + 1, array);
        }
    }
}

当我用 System.out.println(Arrays.toString(array)); 替换注释时，输出是

[0, 0, 4]
[0, 1, 3]
[0, 2, 2]
[0, 3, 1]
[0, 4, 0]
[1, 0, 3]
[1, 1, 2]
[1, 2, 1]
[1, 3, 0]
[2, 0, 2]
[2, 1, 1]
[2, 2, 0]
[3, 0, 1]
[3, 1, 0]
[4, 0, 0]

将穷举增量分布到固定数量的槽中的算法

Algorithm for exhaustive incremental distribution into a fixed number of slots

algorithm

combinations

permutation

pseudocode