一种迭代算法，而不是递归算法，以找到将n分成m个部分的所有方法

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

然而，我可能在使用大数字时使用它，因此需要将其转换为迭代方法。我还不确定如何做到这一点，因为它每次"超级调用"调用自己多次，甚至很难转换为尾调用和累加器，更不用说使用它们转换为迭代形式了。

示例输出:

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 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的函数混淆。

Answer 2

import numpy as np
from itertools import combinations_with_replacement
def f(n, m):
    r = combinations_with_replacement(xrange(n + 1), m - 1)
    return [np.diff([0] + list(x) + [n]).tolist() for x in r]

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

维护一个未完成任务队列。

未完成的作业是一个数字列表，其中第一个元素可以进一步分割。从队列中取出一个作业，以各种可能的方式拆分第一个元素，并将生成的作业添加回队列。

算法如下(折衷伪代码)

Q = new Queue
Q.enqueue ([n])
While not Q.empty:
   l = Q.dequeue()
   Output.append(l)
   h = l.head
   t = l.tail
   If h != 1:
     For each i in 1 .. h-1:
       Q.enqueue ([i,h-i]++t)

Answer 4

这是Python中递归转化为迭代的方法:

def f(n,m):
  stack = [([n] + (m - 1)*[0],0)]
  result = []
  while len(stack) > 0:
    (p,i) = stack.pop()
    if i == m - 1:
      result.append(p)
    else:
      for k in xrange(0,p[i] + 1):
        _p = p[:]
        _p[i] = _p[i] - k
        _p[i + 1] = p[i + 1] + k
        stack.append((_p,i + 1))
  return result
print(f(4,3))
print(f(7,2))