Menu

Subscribe

Integer partition with python and erlang

on erlang, pyhon, algorithm

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition.

For example, 4 can be partitioned in four distinct ways:

3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

More information you can find here and here.

Recursive algorithm with python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import itertools
import uuid

#
# partitioning for integer <<n>>
#
def p0(n, permutate=False, first=True):
    answer = set()
    if not first: answer.add((n,))
    for x in range(1, n):
        for y in p0(n - x, first=False): answer.add(tuple(sorted((x,)+y)))
    if permutate:
        return sum([list(set(list(itertools.permutations(i)))) for i in answer],[])
    else:
        return answer

Recursive algorith with erlang:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
p0(N) -> lists:usort([lists:sort(E)||E<-fl(p0_(N,N,[]))]).
p0_(1,_, _Opts)  -> [[1]];
p0_(N,M, _Opts ) -> 
    Extra = [ [lists:sort(Y++[X])||Y<-p0_(N-X,M, _Opts)] || X<-lists:seq(1,N-1)],
    if N == M -> Extra; true -> [[N]|Extra] end.

fl([])    -> [];
fl([H|T]=L) when is_integer(H),is_list(T) ->
    case is_flat(T) of
        true  -> [lists:flatten(L)];
        false -> fl([expl(H,E) || E <- T]) 
    end;
fl([H|T]) -> fl(H) ++ fl(T);
fl(H)     -> [H].

expl(A,B) when is_list(B) -> [A|B];
expl(_,B) -> B.

is_flat(L) when is_list(L) -> length([E||E<-L, is_list(E)]) < 2;
is_flat(_) -> true.

Another implementation with erlang (using process dictionary). Much faster for big numbers.

1
2
3
4
5
6
7
8
9
10
11
12
p0_1(N)    -> p0_1_(N,N).
p0_1_(1,_) -> [[1]];
p0_1_(N,M) -> 
     Answer = make_ref(),
     if N =/= M -> put(Answer,[[N]]); true -> put(Answer, []) end,
     lists:foreach(fun(X)-> 
         lists:foreach(fun(Y)-> R = get(Answer)++[lists:sort(Y++[X])], put(Answer,R) 
                       end, p0_1_(N-X,M))
     end, lists:seq(1,N-1)),
     Ret = get(Answer), erase(Answer),
     lists:usort(Ret).

If we are test performance of p0 and p0_1 for N=25 with 100000 iterations:

1
2
3
4
    {Time1,_} = timer:tc(fun(_)-> p0(N) end, [100000]),
    io:format("Time1:~p ~n", [Time1]),
    {Time2,_} = timer:tc(fun(_)-> p0_1(N) end, [100000]),
    io:format("Time2:~p ~n", [Time2]).

On my laptopn it will be (time in microseconds):

Time1:184666120 
Time2:30488624

If denominators stricted by given list, for example we can use only 1 and 2 for combinations we have to make some changes. Python implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#
# partitioning for integer <<n>> with denominators from list <<ds>>
#
def p1(n, ds, permutate=False, first=True):
    answer = set()
    if not first and n in ds: answer.add((n,))
    for x in range(1, n):
        if x in ds:
            for y in p1(n - x, ds, first=False): answer.add(tuple(sorted((x,)+y)))
    if permutate:
        return sum([list(set(list(itertools.permutations(i)))) for i in answer],[])
    else:
        return answer

and same algorithm with erlang:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
%
% partitioning for integer <<N>> with denominators from list <<DS>>
%
p1(N,   DS) -> lists:filter(fun(L)-> lists:sum(L)==N end,lists:usort([lists:sort(E)||E<-fl(p1_(N,N,DS))])).
p1_(1,_,DS) -> case lists:member(1,DS) of true -> [[1]];_ -> [] end;
p1_(N,M,DS) ->
    Extra = [ [lists:sort(Y++[X])||Y<-p1_(N-X,M,DS), lists:member(X,DS)] || X<-lists:seq(1,N-1)],
    case {N==M, lists:member(N,DS)} of
        {false, true} -> [[N]|Extra]
        ;_ -> Extra
    end.

fl([])    -> [];
fl([H|T]=L) when is_integer(H),is_list(T) ->
    case is_flat(T) of
        true  -> [lists:flatten(L)];
        false -> fl([expl(H,E) || E <- T]) 
    end;
fl([H|T]) -> fl(H) ++ fl(T);
fl(H)     -> [H].

expl(A,B) when is_list(B) -> [A|B];
expl(_,B) -> B.

is_flat(L) when is_list(L) -> length([E||E<-L, is_list(E)]) < 2;
is_flat(_) -> true.

And another limitation: if we are have limited numbers of denominators:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#
# partitioning for integer <<n>> with limited number of denominators from list <<ds>>
#
def p2(n, ds, permutate=False, first=True):
    answer = set()
    if not first and n in ds: 
        answer.add((n,))
        ds.remove(n)
    for x in range(1, n):
        if x in ds:
            ds.remove(x)
            for y in p2(n - x, list(ds), first=False): answer.add(tuple(sorted((x,)+y)))
    if permutate:
        return sum([list(set(list(itertools.permutations(i)))) for i in answer],[])
    else:
        return answer