一种迭代而非递归算法，可找到将n拆分为m个片段的所有方法 [英] An iterative rather than recursive algorithm to find all ways to split n into m pieces

问题描述

我需要一个带两个整数的函数，假设n和m，其中n> = 0和m> = 1，它返回一个列表列表，其中包含将n分解为m个正整数的所有可能方式（顺序很重要，[4，7，2]与[7，4，2]不同。）

现在，我能够提出一个快速的小递归函数来完成任务，如图所示

I need a function that takes two integers, let's say n and m, where n >= 0 and m >= 1, which returns a list of lists, containing every possible way to split n up into the m positive integer pieces (Order matters, [4, 7, 2] is distinct from [7, 4, 2].)
Now, I was able to come up with a quick little recursive function that does the job, shown below:

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

但是，我可能是大量使用它，因此需要将其转换为迭代方法。我不确定如何做到这一点，因为它在每个超级调用中多次调用自身，这使得很难转换为尾调用和累加器，更不用说使用它们来转换为迭代形式了。

However, I might be using it with large numbers and therefore need to convert it to an iterative method. I haven't been sure how to do this because it calls itself multiple times per 'supercall', making it difficult to even convert to tail calls and accumulators, much less use them to convert to an iterative form.

示例输出：

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]]

等。

推荐答案

下面是使用itertools的一种方法：

Here is a way using 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]))))

以下是一些时间基准，显示了列表转换，排序和函数调用的开销：

Here are several timeit benchmarks showing the overhead for list conversion, sorting and function invocation:

%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（）的基准以进行比较：

Here is a benchmark for @zyxue's numpy-based function f() for comparison:

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

运行您的split（）函数冻结了我的内核，所以我无法计时。请注意，在其中应该将split_function更改为split或将函数名称更改为split_function才能正常工作。 split_function可能是避免与其他名为split的函数混淆的更好选择。

Running your split() function froze my kernel so I was unable to timeit. Note that in it split_function should be changed to split or change the function name to split_function for it to work. split_function may be the better choice to avoid confusion with other functions named split.

这篇关于一种迭代而非递归算法，可找到将n拆分为m个片段的所有方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！