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

Question

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

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

这样的问题有标准算法吗？可以假设总是存在至少一个满足限制条件的分区。

Answer 1

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

• 如果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):

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