找到长度小于或等于 L 的 n 的所有分区

Question

如何找到 n 中长度小于或等于 L 的所有 partitions？

Answer 1

根据给定的代码 here，我们可以包含一个额外的参数 L（默认为 n）。

我们可能天真地在 yield (i,) + p 之前包含 if len((i,) + p) <= L:。但是，由于 len((i,) + p) = 1 + len(p)，n-i 中任何长于 L-1 的分区都将被丢弃。因此，寻找它们会浪费时间。相反，我们应该在查找 n-1 的分区时将 L=L-1 作为参数包含在内。然后我们需要正确处理 L=0 案例，而不是运行主体：

def partitions(n, L=None, I=1):
    if L is None:
        L = n
    
    if L:
        yield (n,)
        for i in range(I, n//2 + 1):
            for p in partitions(n-i, L-1, i):
                yield (i,) + p

现在如果 L=1，for i 循环将被执行，但是 for p 循环中的 none 将被执行，因为 partitions 调用不会产生任何东西；在这种情况下我们根本不需要执行 for i 循环，这样可以节省很多时间：

def partitions(n, L=None, I=1):
    if L is None:
        L = n
    
    if L == 1:
        yield (n,)
    elif L > 1:
        yield (n,)
        for i in range(I, n//2 + 1):
            for p in partitions(n-i, L-1, i):
                yield (i,) + p

找到长度小于或等于 L 的 n 的所有分区

Find all partitions of n of length less-than-or-equal to L

python

combinatorics

python-3.x