生成数字的分区

Question

我需要一个算法来生成所有可能的正数分区,我想出了一个(作为答案发布),但它是指数时间.

该算法应该返回所有可能的方式,数字可以表示为小于或等于其自身的正数之和.例如,对于数字5,结果将是:

• 五
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

所以我的问题是:有更高效的算法吗？

编辑:问题的标题是"数字的总和分解",因为我真的不知道这叫什么.ShreevatsaR指出它们被称为"分区",所以我相应地编辑了问题标题.

Answer 1

它被称为分区.[另见维基百科:分区(数论).]

分区数p(n)呈指数级增长,因此生成所有分区所需的任何操作都必须采用指数时间.

也就是说,你可以比你的代码做得更好.请参阅David Eppstein在Python算法和数据结构中的这个或更新版本.

Answer 2

这是我在Python中的解决方案(指数时间):

q = { 1: [[1]] }

def decompose(n):
    try:
        return q[n]
    except:
        pass

    result = [[n]]

    for i in range(1, n):
        a = n-i
        R = decompose(i)
        for r in R:
            if r[0] <= a:
                result.append([a] + r)

    q[n] = result
    return result

 

>>> decompose(5)
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

Answer 3

当你问更高效的算法时,我不知道要比较哪个.但是这里有一种直接编写的算法(Erlang):

-module(partitions).

-export([partitions/1]).

partitions(N) -> partitions(N, N).

partitions(N, Max) when N > 0 ->
    [[X | P]
     || X <- lists:seq(min(N, Max), 1, -1),
        P <- partitions(N - X, X)];
partitions(0, _) -> [[]];
partitions(_, _) -> [].

它是指数时间(与CanBerkGüder在Python中的解决方案相同)和线性堆栈空间.但是使用相同的技巧,memoization,你可以通过节省一些内存和更少的指数来实现重大改进.(N = 50,速度快十倍)

mp(N) ->
    lists:foreach(fun (X) -> put(X, undefined) end,
          lists:seq(1, N)), % clean up process dictionary for sure
    mp(N, N).

mp(N, Max) when N > 0 ->
    case get(N) of
      undefined -> R = mp(N, 1, Max, []), put(N, R), R;
      [[Max | _] | _] = L -> L;
      [[X | _] | _] = L ->
          R = mp(N, X + 1, Max, L), put(N, R), R
    end;
mp(0, _) -> [[]];
mp(_, _) -> [].

mp(_, X, Max, R) when X > Max -> R;
mp(N, X, Max, R) ->
    mp(N, X + 1, Max, prepend(X, mp(N - X, X), R)).

prepend(_, [], R) -> R;
prepend(X, [H | T], R) -> prepend(X, T, [[X | H] | R]).

无论如何,你应该为你的语言和目的进行基准测试