algorithm - 有限制地将 n 分割为 k 个部分

我需要一种算法，将数字 n 的分区生成为 k 部分，并附加限制，即分区的每个元素必须介于 a 和 b 之间。理想情况下，满足限制的所有可能分区的可能性应该相等。如果分区具有不同顺序的相同元素，则它们被认为是相同的。

例如，对于 n=10 、 k=3 、 a=2 、 b=4 ，只有 {4,4,2} 和 {4,3,3} 作为可能的结果。

是否有针对此类问题的标准算法？可以假设至少有一个满足限制的分区始终存在。

最佳答案

您可以将其实现为递归算法。基本上，递归是这样的:

如果 k == 1 和 a <= n <= b ，则唯一的分区是 [n] ，否则没有

否则，将 x 到 a 的所有元素 b 与 n-x 、 k-1

的所有分区组合起来

防止重复，也用 a

替换下限 x
这是一些 Python(又名可执行伪代码):

def partitions(n, k, a, b):
    if k == 1 and a <= n <= b:
        yield [n]
    elif n > 0 and k > 0:
        for x in range(a, b+1):
            for p in partitions(n-x, k-1, x, b):
                yield [x] + p

print(list(partitions(10, 3, 2, 4)))
# [[2, 4, 4], [3, 3, 4]]

这可以通过分别检查剩余元素的下限和上限的 (k-1)*a 和 (k-1)*b 并相应地限制 x 的范围来进一步改进:

        min_x = max(a, n - (k-1) * b)
        max_x = min(b, n - (k-1) * a)
        for x in range(min_x, max_x+1):

对于具有 3,157 个解决方案的 partitions(110, 12, 3, 12)，这将递归调用的数量从 638,679 减少到 24,135。

关于algorithm - 有限制地将 n 分割为 k 个部分，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41982466/