Это звонило Разделы . [Также посмотрите Википедию: Раздел (теория чисел) .]
количество разделов p (n) растет экспоненциально, таким образом, что-либо, что Вы делаете для генерации весь разделы, должно будет обязательно занять время.
Тем не менее можно добиться большего успеха, чем, что делает код. См. это , или его обновленная версия в Алгоритмы Python и Структуры данных David Eppstein .
Вот мое решение (экспоненциальное время) в 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]]
Когда Вы спрашиваете к более эффективному алгоритму, я не знаю, чтобы выдержать сравнение. Но вот один алгоритм, записанный прямым способом (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(_, _) -> [].
Это экспоненциально вовремя (то же, поскольку Может решение GГј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]).
Так или иначе, необходимо сравнить для языка и целей.