n的k个部分划分（带限制）

Question

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

例如，当n=10，k=3，a=2，b=4时，只有{4,4,2}和{4,3,3}是可能的结果。

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

- Jesús Ros

---

我最近回答了一个非常类似的问题，提供了一个计算条件概率并相应采样的算法：http://stackoverflow.com/q/41871179/2144669 - David Eisenstat

Answer 1

您可以将其实现为递归算法。基本上，递归如下：

- 如果 k == 1 并且 a <= n <= b，则唯一的分区是 [n]，否则没有分区 - 否则，将 a 到 b 中的所有元素 x 与 n-x 的所有分区，k-1 结合起来 - 为了防止重复，还要用 x 替换下限 a 以下是一些 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。

- tobias_k

---

嗯，我猜我错过了你想要一个随机的单个分区，而不是整个列表的部分...好吧，你仍然可以生成它们所有然后随机选择一个。这也将保证每个合法的排列都有相等的可能性。 - tobias_k

Answer 2

如果k和b-a不太大，您可以尝试随机深度优先搜索：

import random

def restricted_partition_rec(n, k, min, max):
    if k <= 0 or n < min:
        return []
    ps = list(range(min, max + 1))
    random.shuffle(ps)
    for p in ps:
        if p > n:
            continue
        elif p < n:
            subp = restricted_partition(n - p, k - 1, min, max)
            if subp:
                return [p] + subp
        elif k == 1:
            return [p]
    return []

def restricted_partition(n, k, min, max):
    return sorted(restricted_partition_rec(n, k, min, max), reverse=True)

print(restricted_partition(10, 3, 2, 4))
>>>
[4, 4, 2]

虽然我不确定在这种情况下所有分区是否具有完全相同的概率。

- jdehesa

---

我感兴趣的值是n从38到110，k从6到12，a=3，b=12。 - Jesús Ros

Answer 3

这是一个使用条件概率的抽样算法示例。

import collections
import random

countmemo = {}


def count(n, k, a, b):
    assert n >= 0
    assert k >= 0
    assert a >= 0
    assert b >= 0
    if k == 0:
        return 1 if n == 0 else 0
    key = (n, k, a, b)
    if key not in countmemo:
        countmemo[key] = sum(
            count(n - c, k - 1, a, c) for c in range(a, min(n, b) + 1))
    return countmemo[key]


def sample(n, k, a, b):
    partition = []
    x = random.randrange(count(n, k, a, b))
    while k > 0:
        for c in range(a, min(n, b) + 1):
            y = count(n - c, k - 1, a, c)
            if x < y:
                partition.append(c)
                n -= c
                k -= 1
                b = c
                break
            x -= y
        else:
            assert False
    return partition


def test():
    print(collections.Counter(
        tuple(sample(20, 6, 2, 5)) for i in range(10000)))


if __name__ == '__main__':
    test()

- David Eisenstat