python - 一种迭代而非递归算法，用于找到将 n 拆分为 m block 的所有方法

Question

我需要一个接受两个整数的函数，比方说 n 和 m，其中 n >= 0 和 m >= 1，它返回一个列表列表，包含将 n 分成 m 个正整数部分的所有可能方法(顺序很重要，[4, 7, 2] 不同于 [7, 4, 2]。)
现在，我能够想出一个快速的小递归函数来完成这项工作，如下所示:

def split(number, elements):
    if elements == 1:
        return [[number]]
    ways = []
    for i in range(0, number + 1):
        for j in split_number(number - i, elements - 1):
            values.append([i] + j)
    return values

但是，我可能会将它用于大量数据，因此需要将其转换为迭代方法。我不确定如何执行此操作，因为它在每个“ super 调用”中多次调用自身，这使得它甚至很难转换为尾调用和累加器，更不用说使用它们转换为迭代形式了。

示例输出:

split(7, 2) -> [[0, 7], [1, 6], [2, 5], [3, 4], [4, 3], [5, 2], [6, 1], [7, 0]]
split(4, 3) -> [[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]]

等等

Answer 1

这是一种使用 itertools 的方法:

def chainsplit(n,p):
    return sorted(list(set(chain.from_iterable([list(permutations(i,len(i))) 
        for i in list(combinations_with_replacement(range(n+1),p)) if sum(i) == n]))))

这里有几个 timeit 基准测试显示了列表转换、排序和函数调用的开销:

%timeit set(chain.from_iterable([list(permutations(i,len(i))) for i in list(combinations_with_replacement(range(5),3)) if sum(i) == 4]))
10000 loops, best of 3: 20 µs per loop

%timeit list(set(chain.from_iterable([list(permutations(i,len(i))) for i in list(combinations_with_replacement(range(5),3)) if sum(i) == 4])))
10000 loops, best of 3: 20.4 µs per loop

%timeit sorted(list(set(chain.from_iterable([list(permutations(i,len(i))) for i in list(combinations_with_replacement(range(5),3)) if sum(i) == 4]))))
10000 loops, best of 3: 25 µs per loop

%timeit chainsplit(4,3)
10000 loops, best of 3: 26.4 µs per loop

这里是@zyxue 的基于 numpy 的函数 f() 的基准进行比较:

timeit f(4,3)
10000 loops, best of 3: 133 µs per loop

运行你的 split() 函数卡住了我的内核，所以我无法计时。注意里面的split_function要改成split或者把函数名改成split_function才能生效。 split_function 可能是更好的选择，以避免与其他名为 split 的函数混淆。